Document Open Access Logo

Approximating Unique Games Using Low Diameter Graph Decomposition

Authors Vedat Levi Alev, Lap Chi Lau

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.18.pdf
  • Filesize: 0.51 MB
  • 15 pages

Document Identifiers

Author Details

Vedat Levi Alev
Lap Chi Lau

Cite AsGet BibTex

Vedat Levi Alev and Lap Chi Lau. Approximating Unique Games Using Low Diameter Graph Decomposition. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.18

Abstract

We design approximation algorithms for Unique Gmeas when the constraint graph admits good low diameter graph decomposition. For the M2Lin(k) problem in K(r)-minor free graphs, when there is an assignment satisfying 1-eps fraction of constraints, we present an algorithm that produces an assignment satisfying 1-O(r*eps) 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(eps)) 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 M2Lin(k) problem and by sqrt(log g) in the general problem. The former result generalizes the result of Gupta-Talwar for Unique Games in the M2Lin(k) case, and the latter result generalizes the result of Trevisan for general Unique Games.
Keywords
  • Unique Games
  • Low Diameter Graph Decomposition
  • Bounded Genus Graphs
  • Fixed Minor Free Graphs
  • Approximation Algorithms
  • Linear Programming

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, and Kunal Talwar. Cops, robbers, and threatening skeletons: Padded decomposition for minor-free graphs. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing. ACM, 2014. Google Scholar
  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. Google Scholar
  3. Naman Agarwal. Unique games conjecture: The boolean hypercube and connections to graph lifts. Master’s thesis, University of Illinois at Urbana-Champaign, 2014. Google Scholar
  4. Naman Agarwal, Guy Kindler, Alexandra Kolla, and Luca Trevisan. Unique games on the hypercube. Chicago Journal of Theoretical Computer Science, 2015, 2015. Google Scholar
  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 Foundations of Computer Science. IEEE, 2010. Google Scholar
  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. Google Scholar
  7. Brenda S. Baker. Approximation algorithms for np-complete problems on planar graphs. Journal of the ACM, 41, 1994. Google Scholar
  8. Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, 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. Google Scholar
  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. Google Scholar
  10. Punyashloka Biswal, James R. Lee, and Satish Rao. Eigenvalue bounds, spectral partitioning, and metrical deformations via flows. Journal of the ACM, 57, 2010. Google Scholar
  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 Computing. ACM, 2006. Google Scholar
  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. Google Scholar
  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. Google Scholar
  14. Erik D. Demaine and MohammadTaghi Hajiaghayi. The bidimensionality theory and its algorithmic applications. The Computer Journal, 51, 2008. Google Scholar
  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. Google Scholar
  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. Google Scholar
  17. Jean Fonlupt, Ali Ridha Mahjoub, and J. P. Uhry. Compositions in the bipartite subgraph polytope. Discrete mathematics, 105, 1992. Google Scholar
  18. Anupam Gupta and Kunal Talwar. Approximating unique games. In Proceedings of the 70th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2006. Google Scholar
  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. Google Scholar
  20. Frank Hadlock. Finding a maximum cut of a planar graph in polynomial time. SIAM Journal on Computing, 4, 1975. Google Scholar
  21. Jonathan A. Kelner. Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus. SIAM Journal on Computing, 35, 2006. Google Scholar
  22. Jonathan A. Kelner, James R. Lee, Gregory N. Price, and Shang-Hua Teng. Metric uniformization and spectral bounds for graphs. Geometric and Functional Analysis, 21, 2011. Google Scholar
  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. Google Scholar
  24. Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell. Optimal inapproximability results for max-cut and other 2-variable csps? SIAM Journal on Computing, 37, 2007. Google Scholar
  25. Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2- ε. Journal of Computer and System Sciences, 74, 2008. Google Scholar
  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. Google Scholar
  27. Alexandra Kolla. Spectral algorithms for unique games. Computational Complexity, 20, 2011. Google Scholar
  28. Lap Chi Lau, Ramamoorthi Ravi, and Mohit Singh. Iterative methods in combinatorial optimization, volume 46. Cambridge University Press, 2011. Google Scholar
  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. Google Scholar
  30. Lászlo Lovász, Martin Grötschel, and Alexander Schrijver. Geometric algorithms and combinatorial optimization. Springer-Verlag, Berlin, 1988. Google Scholar
  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. Google Scholar
  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. Google Scholar
  33. Prasad Raghavendra, David Steurer, and Madhur Tulsiani. Reductions between expansion problems. In Proceedings of the 27th IEEE Annual Conference on Computational Complexity. IEEE, 2012. Google Scholar
  34. Daniel A. Spielman and Shang-Hua Teng. Spectral partitioning works: Planar graphs and finite element meshes. Linear Algebra and its Applications, 421, 2007. Google Scholar
  35. David Steurer and Nisheeth K. Vishnoi. Connections between unique games and multicut. Electronic Colloquium on Computational Complexity, 16, 2009. Google Scholar
  36. Luca Trevisan. Approximation algorithms for unique games. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 2005. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact