New approximation guarantee for chromatic number

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

New approximation guarantee for chromatic number

Full text

Pdf (266 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-eighth annual ACM symposium on Theory of computing table of contents

Seattle, WA, USA

SESSION: Session 5A table of contents

Pages: 215 - 224

Year of Publication: 2006

ISBN:1-59593-134-1

Authors

Sanjeev Arora	Princeton University, Princeton, NJ
Eden Chlamtac	Princeton University, Princeton, NJ

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 77, Citation Count: 4

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1132516.1132548 What is a DOI?

ABSTRACT

We describe how to color every 3-colorable graph with O(n^0.2111) colors, thus improving an algorithm of Blum and Karger from almost a decade ago. Our analysis uses new geometric ideas inspired by the recent work of Arora, Rao, and Vazirani on SPARSEST CUT, and these ideas show promise of leading to further improvements.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Sanjeev Arora , Satish Rao , Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.222-231, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007355]
	2	Avrim Blum, New approximation algorithms for graph coloring, Journal of the ACM (JACM), v.41 n.3, p.470-516, May 1994 [doi>10.1145/176584.176586]
	3	Avrim Blum , David Karger, An Õ(n3/14)-coloring algorithm for 3-colorable graphs, Information Processing Letters, v.61 n.1, p.49-53, Jan. 14, 1997 [doi>10.1016/S0020-0190(96)00190-1]
	4	C. Borell. The Brunn-Minkowski inequality in gauss space. Invent. Math., 30:207--216, 1975.
	5	Shuchi Chawla , Robert Krauthgamer , Ravi Kumar , Yuval Rabani , D. Sivakumar, On the Hardness of Approximating Multicut and Sparsest-Cut, Proceedings of the 20th Annual IEEE Conference on Computational Complexity, p.144-153, June 11-15, 2005 [doi>10.1109/CCC.2005.20]
	6	Irit Dinur , Elchanan Mossel , Oded Regev, Conditional hardness for approximate coloring, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132567]
	7	Uriel Feige , Michael Langberg , Gideon Schechtman, Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers, SIAM Journal on Computing, v.33 n.6, p.1338-1368, 2004 [doi>10.1137/S0097539703431391]
	8	Michel X. Goemans , David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), v.42 n.6, p.1115-1145, Nov. 1995 [doi>10.1145/227683.227684]
	9	J. Hastad. Clique is hard to approximate within n1-ε. Acta Math., 182:105--142, 1999.
	10	Johan Håstad, Some optimal inapproximability results, Journal of the ACM (JACM), v.48 n.4, p.798-859, July 2001 [doi>10.1145/502090.502098]
	11	David Karger , Rajeev Motwani , Madhu Sudan, Approximate graph coloring by semidefinite programming, Journal of the ACM (JACM), v.45 n.2, p.246-265, March 1998 [doi>10.1145/274787.274791]
	12	Howard Karloff , Uri Zwick, A 7/8-Approximation Algorithm for MAX 3SAT?, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.406, October 19-22, 1997
	13	Subhash Khot , Guy Kindler , Elchanan Mossel , Ryan O'Donnell, Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.146-154, October 17-19, 2004 [doi>10.1109/FOCS.2004.49]
	14	Subhash A. Khot , Nisheeth K. Vishnoi, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into \ell 1, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.53-62, October 23-25, 2005 [doi>10.1109/SFCS.2005.74]
	15	Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999 [doi>10.1145/331524.331526]
	16	V. Sudakov and B. Tsirel'son. Extremal properties of half-spaces for spherically invariant measures. Soviet Math, 9:9--18, 1978. Translated from Zap. Nauch. Sem. L.O.M.I 41:14--24, 1964
	17	Avi Wigderson, Improving the performance guarantee for approximate graph coloring, Journal of the ACM (JACM), v.30 n.4, p.729-735, Oct. 1983 [doi>10.1145/2157.2158]

CITED BY 4

	Per Austrin, Balanced max 2-sat might not be the hardest, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Ken-ichi Kawarabayashi , Erik D. Demaine , MohammadTaghi Hajiaghayi, Additive approximation algorithms for list-coloring minor-closed class of graphs, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1166-1175, January 04-06, 2009, New York, New York
	Julia Böttcher , Dan Vilenchik, On the tractability of coloring semirandom graphs, Information Processing Letters, v.108 n.3, p.143-149, October, 2008
	Ken-ichi Kawarabayashi , Bruce Reed, Hadwiger's conjecture is decidable, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA