Approximating unique games using low diameter graph decomposition. (English) Zbl 1467.68217
Jansen, Klaus (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 20th international workshop, APPROX 2017 and 21st international workshop, RANDOM 2017, Berkeley, CA, USA, August 16–18, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 81, Article 18, 15 p. (2017).
Summary: We design approximation algorithms for Unique Games when the constraint graph admits good
low diameter graph decomposition. For the Max-2Lin\(_k\) problem in \(K_r\)-minor free graphs, when there is an assignment satisfying \(1-\varepsilon\) fraction of constraints, we present an algorithm that produces an assignment satisfying \(1- O(r\varepsilon)\) fraction of constraints, with the approximation ratio independent of the alphabet size. A corollary is an improved approximation algorithm for the Min-UnCut problem for \(K_r\)-minor free graphs. For general Unique Games in \(K_r\)-minor free graphs, we provide another algorithm that produces an assignment satisfying \(1-O(r\sqrt{\varepsilon})\) fraction of constraints.
Our approach is to round a linear programming relaxation to find a minimum subset of edges that intersects all the inconsistent cycles. We show that it is possible to apply the low diameter graph decomposition technique on the constraint graph directly, rather than to work on the label extended graph as in previous algorithms for Unique Games. The same approach applies when the constraint graph is of genus \(g\), and we get similar results with \(r\) replaced by \(\log g\) in the Max-2Lin\(_k\) problem and by \(\log g\) in the general problem. The former result generalizes the result of Gupta-Talwar for Unique Games in the Max-2Lin\(_k\) case, and the latter result generalizes the result of Trevisan for general Unique Games.
For the entire collection see [Zbl 1372.68012].
Our approach is to round a linear programming relaxation to find a minimum subset of edges that intersects all the inconsistent cycles. We show that it is possible to apply the low diameter graph decomposition technique on the constraint graph directly, rather than to work on the label extended graph as in previous algorithms for Unique Games. The same approach applies when the constraint graph is of genus \(g\), and we get similar results with \(r\) replaced by \(\log g\) in the Max-2Lin\(_k\) problem and by \(\log g\) in the general problem. The former result generalizes the result of Gupta-Talwar for Unique Games in the Max-2Lin\(_k\) case, and the latter result generalizes the result of Trevisan for general Unique Games.
For the entire collection see [Zbl 1372.68012].
MSC:
| 68W25 | Approximation algorithms |
| 68R10 | Graph theory (including graph drawing) in computer science |
Keywords:
unique games; low-diameter graph decomposition; bounded-genus graphs; fixed minor-free graphs; approximation algorithms; linear programmingReferences:
| [1] | Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, and Kunal Talwar. Cops, robbers, and threatening skeletons: Padded decomposition for minor-free graphs. In Pro-ceedings of the 46th Annual ACM Symposium on Theory of Computing. ACM, 2014. APPROX/RANDOM’17 18:14 · Zbl 1315.05130 |
| [2] | Amit Agarwal, Moses Charikar, Konstantin Makarychev, and Yury Makarychev. O(sqrt(log n)) approximation algorithms for min uncut. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005. · Zbl 1192.68864 |
| [3] | Naman Agarwal. Unique games conjecture: The boolean hypercube and connections to graph lifts. Master’s thesis, University of Illinois at Urbana-Champaign, 2014. |
| [4] | Naman Agarwal, Guy Kindler, Alexandra Kolla, and Luca Trevisan. Unique games on the hypercube. Chicago Journal of Theoretical Computer Science, 2015, 2015. · Zbl 1336.68092 |
| [5] | Sanjeev Arora, Boaz Barak, and David Steurer. Subexponential algorithms for unique games and related problems. In Proceedings of the 51st Annual IEEE Symposium on Found-ations of Computer Science. IEEE, 2010. · Zbl 1426.05159 |
| [6] | Sanjeev Arora, Subhash A. Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, and Nisheeth K. Vishnoi. Unique games on expanding constraint graphs are easy. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing. ACM, 2008. · Zbl 1231.68147 |
| [7] | Brenda S. Baker. Approximation algorithms for np-complete problems on planar graphs. Journal of the ACM, 41, 1994. · Zbl 0807.68067 |
| [8] | Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Naga-rajan, Joseph Naor, and Roy Schwartz. Min-max graph partitioning and small set expansion. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science. IEEE, 2011. · Zbl 1292.05126 |
| [9] | Boaz Barak, Prasad Raghavendra, and David Steurer. Rounding semidefinite programming hierarchies via global correlation. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science. IEEE, 2011. · Zbl 1292.90226 |
| [10] | Punyashloka Biswal, James R. Lee, and Satish Rao. Eigenvalue bounds, spectral partition-ing, and metrical deformations via flows. Journal of the ACM, 57, 2010. · Zbl 1327.05199 |
| [11] | Moses Charikar, Konstantin Makarychev, and Yury Makarychev. Near-optimal algorithms for unique games. In Proceedings of the 38th Annual ACM Symposium on Theory of Com-puting. ACM, 2006. · Zbl 1301.68267 |
| [12] | Eden Chlamtac, Konstantin Makarychev, and Yury Makarychev. How to play unique games using embeddings. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 2006. · Zbl 1314.68401 |
| [13] | Erik D. Demaine, Mohammad Taghi Hajiaghayi, and Ken ichi Kawarabayashi. Algorithmic graph minor theory: Decomposition, approximation, and coloring. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005. |
| [14] | Erik D. Demaine and MohammadTaghi Hajiaghayi. The bidimensionality theory and its algorithmic applications. The Computer Journal, 51, 2008. · Zbl 1174.05115 |
| [15] | Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing. ACM, 2003. · Zbl 1192.68977 |
| [16] | Jittat Fakcharoenphol and Kunal Talwar. An improved decomposition theorem for graphs excluding a fixed minor. Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques. Springer Berlin Heidelberg, 2003. · Zbl 1279.05053 |
| [17] | Jean Fonlupt, Ali Ridha Mahjoub, and J. P. Uhry. Compositions in the bipartite subgraph polytope. Discrete mathematics, 105, 1992. · Zbl 0771.05092 |
| [18] | Anupam Gupta and Kunal Talwar. Approximating unique games. In Proceedings of the 70th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2006. · Zbl 1192.91012 |
| [19] | Venkatesan Guruswami and Ali Kemal Sinop. Lasserre hierarchy and approximation schemes for graph partitioning and quadratic integer programming with psd objectives. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science. IEEE, 2011. · Zbl 1292.90222 |
| [20] | Frank Hadlock. Finding a maximum cut of a planar graph in polynomial time. SIAM Journal on Computing, 4, 1975. · Zbl 0321.05120 |
| [21] | Jonathan A. Kelner. Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus. SIAM Journal on Computing, 35, 2006. · Zbl 1096.05048 |
| [22] | Jonathan A. Kelner, James R. Lee, Gregory N. Price, and Shang-Hua Teng. Metric uni-formization and spectral bounds for graphs. Geometric and Functional Analysis, 21, 2011. · Zbl 1229.05094 |
| [23] | Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the 34th Annual ACM Symposium on Theory of computing. ACM, 2002. · Zbl 1192.68367 |
| [24] | Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapprox-imability results for max-cut and other 2-variable csps? SIAM Journal on Computing, 37, 2007. · Zbl 1135.68019 |
| [25] | Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-ε. Journal of Computer and System Sciences, 74, 2008. · Zbl 1133.68061 |
| [26] | Philip Klein, Serge A. Plotkin, and Satish Rao. Excluded minors, network decomposition, and multicommodity flow. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing, 1993. · Zbl 1310.90017 |
| [27] | Alexandra Kolla. Spectral algorithms for unique games. Computational Complexity, 20, 2011. · Zbl 1234.68120 |
| [28] | Lap Chi Lau, Ramamoorthi Ravi, and Mohit Singh. Iterative methods in combinatorial optimization, volume 46. Cambridge University Press, 2011. · Zbl 1247.90002 |
| [29] | James R. Lee and Anastasios Sidiropoulos. Genus and the geometry of the cut graph. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2010. · Zbl 1288.05062 |
| [30] | Lászlo Lovász, Martin Grötschel, and Alexander Schrijver. Geometric algorithms and com-binatorial optimization. Springer-Verlag, Berlin, 1988. · Zbl 0634.05001 |
| [31] | Prasad Raghavendra. Optimal algorithms and inapproximability results for every csp? In Proceedings of the 40th Annual ACM Symposium on Theory of Computing. ACM, 2008. · Zbl 1231.68142 |
| [32] | Prasad Raghavendra and David Steurer. Graph expansion and the unique games conjecture. In Proceedings of the 42nd ACM Symposium on Theory of Computing. ACM, 2010. · Zbl 1293.05373 |
| [33] | Prasad Raghavendra, David Steurer, and Madhur Tulsiani. Reductions between expansion problems. In Proceedings of the 27th IEEE Annual Conference on Computational Complex-ity. IEEE, 2012. |
| [34] | Daniel A. Spielman and Shang-Hua Teng. Spectral partitioning works: Planar graphs and finite element meshes. Linear Algebra and its Applications, 421, 2007. · Zbl 1122.05062 |
| [35] | David Steurer and Nisheeth K. Vishnoi. Connections between unique games and multicut. Electronic Colloquium on Computational Complexity, 16, 2009. |
| [36] | Luca Trevisan. Approximation algorithms for unique games. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 2005. · Zbl 1213.68320 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
