首页    期刊浏览 2024年12月11日 星期三
登录注册

文章基本信息

  • 标题:Connections Between Unique Games and Multicut
  • 本地全文:下载
  • 作者:David Steurer ; Nisheeth Vishnoi
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2009
  • 卷号:2009
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    In this paper we demonstrate a close connection between UniqueGames andMultiCut.%In MultiCut, one is given a ``network graph'' and a ``demandgraph'' on the same vertex set and the goal is to remove as fewedges from the network graph as possible such that every twovertices connected by a demand edge are separated.%On the other hand, UniqueGames is a certain family of constraintsatisfaction problems.In one direction, we show that, at least with respect to currentalgorithmic techniques, MultiCut is not harder than UniqueGames.%Specifically, we can adapt most known algorithms for UniqueGames towork for MultiCut and obtain new approximation guarantees forMultiCut that depend on the maximum degree of the demand graph.This degree plays the same role as the alphabet size plays inapproximation guarantees for UniqueGames.

    In the other direction, we show that MultiCut is not easier thanUniqueGames (-max-2-lin to be precise).We exhibit a reduction from UniqueGames to MultiCut so that the fraction ofedges in the optimal multicut is up to a factor of 2 equal to thefraction of constraint violated by the optimal assignment for theUniqueGames instance.In contrast to the vast majority of Unique Games reductions whoseanalysis relies on Fourier analysis and isoperimetric inequalities,this reduction is simple and the analysis is elementary.Further, the maximum degree of the demand graph in the instanceproduced by the reduction is less than the size of the alphabet sizein the Unique Games instance.

    Our results rely on a simple but previously unknown characterizationof multicut in terms of 1 metrics.

  • 关键词:Multicut; Unique Games
国家哲学社会科学文献中心版权所有