{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:25:19Z","timestamp":1787340319541,"version":"build-2736575974"},"reference-count":38,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>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 $\\rho$ is the expected fraction of constraints satisfied by a random ordering, then obtaining a $\\rho'$ approximation for any $\\rho'&gt;\\rho$ is UG-hard. For the simplest OCSP, the Maximum Acyclic Subgraph (MAS) problem, this implies that obtaining a $\\rho$-approximation for any constant $\\rho&gt;1\/2$ is UG-hard. Specifically, for every constant $\\varepsilon&gt;0$ the following holds: given a directed graph G that has an acyclic subgraph consisting of a fraction $(1-\\varepsilon)$ of its edges, it is UG-hard to find one with more than $(1\/2+\\varepsilon)$ 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\\subseteq S_k$ of permutations on $\\{1,2,\\dots,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 $\\Pi$. A random ordering of V is expected to satisfy a $\\rho=\\frac{|\\Pi|}{k!}$ fraction. We show that, for any fixed k, it is hard to obtain a $\\rho'$-approximation for $\\Pi$-OCSP for any $\\rho'&gt;\\rho$. The result is in fact stronger: we show that for every $\\Lambda\\subseteq\\Pi\\subseteq S_k$, and an arbitrarily small $\\varepsilon$, it is hard to distinguish instances where a $(1-\\varepsilon)$ fraction of the constraints can be ordered according to $\\Lambda$ from instances where at most a $(\\rho+\\varepsilon)$ 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.<\/jats:p>","DOI":"10.1137\/090756144","type":"journal-article","created":{"date-parts":[[2011,6,24]],"date-time":"2011-06-24T12:43:30Z","timestamp":1308919410000},"page":"878-914","source":"Crossref","is-referenced-by-count":47,"title":["Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant"],"prefix":"10.1137","volume":"40","author":[{"given":"Venkatesan","family":"Guruswami","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Johan","family":"H\u00c5stad","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rajsekar","family":"Manokaran","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Prasad","family":"Raghavendra","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Moses","family":"Charikar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,6,23]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1154"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/070711670"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/100783534"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0272-6"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0864"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"M. Charikar, V. Guruswami, and R. Manokaran,\n                      Every permutation CSP of arity\n                      3\n                      is approximation resistant\n                      , in Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009, pp. 62\u201373.","DOI":"10.1109\/CCC.2009.29"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"M. Charikar, K. Makarychev, and Y. Makarychev,\n                      On the advantage over random for maximum acyclic subgraph\n                      , in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007, pp. 625\u2013633.","DOI":"10.1109\/FOCS.2007.65"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"M. Charikar, Y. Makarychev, and K. Makarychev,\n                      Near-optimal algorithms for unique games\n                      , in Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006, pp. 205\u2013214.","DOI":"10.1145\/1132516.1132547"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480195296221"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20026"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009191"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"U. Feige and M. X. Goemans,\n                      Approximating the value of two proper proof systems, with applications to MAX-\n                      2\n                      SAT and MAX-DICUT\n                      , in Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995, pp. 182\u2013189.","DOI":"10.1109\/ISTCS.1995.377033"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"V. Guruswami, R. Manokaran, and P. Raghavendra,\n                      Beating the random ordering is hard: Inapproximability of maximum acyclic subgraph\n                      , in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008, pp. 573\u2013582.","DOI":"10.1109\/FOCS.2008.51"},{"key":"R15","unstructured":"V. Guruswami and Y. Zhou,\n                      Approximating Bounded Occurrence Ordering CSPs\n                      , manuscript, 2010."},{"key":"R16","doi-asserted-by":"crossref","unstructured":"G. Hast,\n                      Beating a Random Assignment\n                      , Ph.D. thesis, Royal Institute of Technology, Stockholm, Sweden, 2005.","DOI":"10.1007\/11538462_12"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-008-0256-y"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0262-8"},{"key":"R20","unstructured":"M. Isaksson and E. Mossel,\n                      Maximally stable Gaussian partitions with discrete applications\n                      , Israel J. Math., to appear."},{"key":"R21","unstructured":"A. Karazanov,\n                      On the minimal number of arcs of a digraph meeting all its directed cutsets\n                      , Graph Theory Newsletters, 8 (1979)."},{"key":"R22","doi-asserted-by":"crossref","unstructured":"R. M. Karp,\n                      Reducibility among combinatorial problems\n                      , in Complexity of Computer Computations, Plenum, New York, 1972, pp. 85\u2013103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"S. Khot,\n                      On the power of unique\n                      2\n                      -prover\n                      1\n                      -round games\n                      , in Proceedings of the 34th Annual ACM Symposium on Theory of Computing, 2002, pp. 767\u2013775.","DOI":"10.1145\/509907.510017"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447372"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.019"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"S. Khot and N. K. Vishnoi,\n                      The Unique Games conjecture, integrality gap for cut problems and embeddability of negative type metrics into $l_{1}$\n                      , in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005, pp. 53\u201362.","DOI":"10.1109\/SFCS.2005.74"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-17.3.369"},{"key":"R28","unstructured":"Y. Makarychev,\n                      Simple Linear Time Approximation Algorithm for Betweenness\n                      , Microsoft Research Technical report MSR-TR-2009-74, 2009."},{"key":"R29","doi-asserted-by":"crossref","unstructured":"R. Manokaran, J. S. Naor, P. Raghavendra, and R. Schwartz,\n                      SDP gaps and UGC hardness for multiway cut,\n                      0\n                      -extension and metric labelling\n                      , in Proceedings of the 40th ACM Symposium on Theory of Computing, 2008, pp. 11\u201320.","DOI":"10.1145\/1374376.1374379"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"E. Mossel,\n                      Gaussian bounds for noise correlation of functions and tight analysis of long codes\n                      , in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008, pp. 156\u2013165.","DOI":"10.1109\/FOCS.2008.44"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2010.171.295"},{"key":"R32","unstructured":"A. Newman,\n                      Approximating the Maximum Acyclic Subgraph\n                      , Master's thesis, MIT, Cambridge, MA, 2000."},{"key":"R33","doi-asserted-by":"crossref","unstructured":"A. Newman,\n                      Cuts and orderings: On semidefinite relaxations for the linear ordering problem\n                      , in Proceedings of APPROX-RANDOM, 2004, pp. 195\u2013206.","DOI":"10.1007\/978-3-540-27821-4_18"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"R35","doi-asserted-by":"crossref","unstructured":"P. Raghavendra,\n                      Optimal algorithms and inapproximability results for every CSP?\n                      , in Proceedings of the 40th ACM Symposium on Theory of Computing, 2008, pp. 245\u2013254.","DOI":"10.1145\/1374376.1374414"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90022-3"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200760"},{"key":"R38","unstructured":"U. Zwick,\n                      Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint\n                      , in Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998, pp. 201\u2013210."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090756144","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:29:49Z","timestamp":1787336989000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090756144"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/090756144"],"URL":"https:\/\/doi.org\/10.1137\/090756144","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}