Change search
ReferencesLink to record
Permanent link

Direct link
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-5379-345X
Show others and affiliations
2011 (English)In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 40, no 3, 878-914 p.Article in journal (Refereed) Published
Abstract [en]

We prove that, assuming the Unique Games conjecture (UGC), every problem in the class of ordering constraint satisfaction problems (OCSPs) 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 rho' approximation for any rho' > rho is UG-hard. For the simplest OCSP, the MAXIMUM ACYCLIC SUBGRAPH (MAS) problem, this implies that obtaining a.-approximation for any constant rho > 1/2 is UG-hard. Specifically, for every constant epsilon > 0 the following holds: given a directed graph G that has an acyclic subgraph consisting of a fraction (1-epsilon) of its edges, it is UG-hard to find one with more than (1/2 + epsilon) of its edges. Note that it is trivial to find an acyclic subgraph with 1/2 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 Pi subset of S-k of permutations on {1, 2, ... ,k}. 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 rho = vertical bar Pi vertical bar/k! fraction. We show that, for any fixed k, it is hard to obtain rho'-approximation for Pi-OCSP for any rho' > rho. The result is in fact stronger: we show that for every Lambda subset of Pi subset of S-k, and an arbitrarily small epsilon, it is hard to distinguish instances where a (1 - epsilon) fractionof the constraints can be ordered according to. from instances where at most a (rho + epsilon) fraction can be ordered as in Pi. A special case of our result is that the BETWEENNESS problem is hard to approximate beyond a factor 1/3. 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.

Place, publisher, year, edition, pages
2011. Vol. 40, no 3, 878-914 p.
Keyword [en]
MAXIMUM ACYCLIC SUBGRAPH, feedback arc set, Unique Games conjecture, hardness of approximation, integrality gaps
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-36217DOI: 10.1137/090756144ISI: 000292108900014ScopusID: 2-s2.0-79960378967OAI: diva2:430723
QC 20110811Available from: 2011-07-12 Created: 2011-07-11 Last updated: 2012-02-14Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Håstad, Johan
By organisation
Theoretical Computer Science, TCS
In the same journal
SIAM journal on computing (Print)
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 46 hits
ReferencesLink to record
Permanent link

Direct link