文章基本信息

标题：Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant
本地全文：下载
作者：Venkatesan Guruswami ; Johan Hastad ; Rajsekar Manokaran 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2011
卷号：2011
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We prove that, assuming the Unique Games Conjecture (UGC), every problem in the class of ordering constraint satisfaction problems (OCSP) where each constraint has constant arity is approximation resistant. In other words, we show that if is the expected fraction of constraints satisfied by a random ordering, then obtaining a approximation, for any is UG-hard. For the simplest ordering CSP, the \mas (MAS) problem, this implies that obtaining a -approximation, for any constant 12 is UG-hard. Specifically, for every constant \eps0 the following holds: given a directed graph G that has an acyclic subgraph consisting of a fraction (1−\eps) of its edges, it is UG-hard to find one with more than (12+\eps) of its edges. Note that it is trivial to find an acyclic subgraph with 12 the edges, by taking either the forward or backward edges in an arbitrary ordering of the vertices of G. The MAS problem has been well studied and beating the random ordering for MAS has been a basic open problem. An OCSP of arity k is specified by a subset Sk of permutations on 12k . An instance of such an OCSP is a set V and a collection of constraints each of which is an ordered k-tuple of V. The objective is to find a global linear ordering of V while maximizing the number of constraints ordered as in . A random ordering of V is expected to satisfy a =k! fraction. We show that, for any fixed k, it is hard to obtain a -approximation for -OCSP for any . The result is in fact stronger: we show that for every Sk, and an arbitrarily small \eps, it is hard to distinguish instances where a (1−\eps) fraction of the constraints can be ordered according to ; from instances where at most a +\eps fraction can be ordered as in . A special case of our result is that the {\em Betweenness} problem is hard to approximate beyond a factor 13 . The results naturally generalize to OCSPs which assign a payoff to the different permutations. Finally, our results imply (unconditionally) that a simple semidefinite relaxation for MAS does not suffice to obtain a better approximation.