• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Integer Programming and Combinatorial Optimization >Local Guarantees in Graph Cuts and Clustering
【24h】

Local Guarantees in Graph Cuts and Clustering

机译：图中的本地保证剪切和聚类

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Correlation Clustering is an elegant model that captures fundamental graph cut problems such as Min s - t Cut, Multiway Cut, and Multicut, extensively studied in combinatorial optimization. Here, we are given a graph with edges labeled + or - and the goal is to produce a clustering that agrees with the labels as much as possible: + edges within clusters and - edges across clusters. The classical approach towards Correlation Clustering (and other graph cut problems) is to optimize a global objective. We depart from this and study local objectives: minimizing the maximum number of disagreements for edges incident on a single node, and the analogous max min agreements objective. This naturally gives rise to a family of basic min-max graph cut problems. A prototypical representative is Min Max s - t Cut: find an s - t cut minimizing the largest number of cut edges incident on any node. We present the following results: (1) an O({the square root of}n)-approximation for the problem of minimizing the maximum total weight of disagreement edges incident on any node (thus providing the first known approximation for the above family of min-max graph cut problems), (2) a remarkably simple 7-approximation for minimizing local disagreements in complete graphs (improving upon the previous best known approximation of 48), and (3) a 1/(2+ε)-approximation for maximizing the minimum total weight of agreement edges incident on any node, hence improving upon the 1/(4+ε)-approximation that follows from the study of approximate pure Nash equilibria in cut and party affiliation games.
机译：相关聚类是一个优雅的模型，捕获基本图形的问题，如Min S-T切割，多道切割和多乳，广泛地研究了组合优化。在这里，我们被赋予标有边缘+或 - 的图形，并且目标是产生一个聚类，它尽可能多地与标签一致：+边缘在群集中的边缘。相关聚类（和其他图表切割问题）的经典方法是优化全局目标。我们离开了这个并研究了本地目标：最大限度地减少在单个节点上发生的边缘的最大分歧，以及类似的MAX MIN协议目标。这自然会产生一个基本的MIN-MAX图削减问题。原型代表是MIN MAX S-T切割：发现最小化入射在任何节点上最大的切割边缘的S-T切割。我们提出以下结果：（1）（1）一个（{n的平方根） - 用于最小化入射在任何节点上的分歧边缘的最大总重量的问题（从而为上述家庭提供第一个已知近似的问题MIN-MAX图削减问题），（2）显着简单的7近似，用于最小化完整图表中的局部分歧（改善先前最着名的近似48），以及（3）1 /（2 +ε） - 估计为了最大化入射在任何节点上的协议边缘的最小总重量，因此改善了1 /（4 +ε）的千次纯纳均衡研究中的1 /（4 +ε） - 截至裁员和党的联系游戏的研究。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号