A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems (extended abstract)

Full text

Pdf (1.08 MB)

Source

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

Portland, Oregon, United States

Pages: 38 - 47

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

Artur Czumaj	Dept. of Computer and Information Science, New Jersey Institute of Technology, University Heights, Newark, NJ
Christian Scheideler	Dept. of Mathematics & Computer Science, and Heinz Nixdorf Institute, Paderborn University, 33095 Paderborn, Germany

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 53, Citation Count: 6

Additional Information:

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/335305.335310 What is a DOI?

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	N. Alon. A parallel algorithmic version of the local lemma. Random Structures and Algorithms, 2(4):367- 387, 1991.
	2	Noga Alon , Amotz Bar-Noy , Nathan Linial , David Peleg, A lower bound for radio broadcast, Journal of Computer and System Sciences, v.43 n.2, p.290-298, Oct. 1991 [doi>10.1016/0022-0000(91)90015-W]
	3	N. Alon, C. McDiarmid, and B. Reed. Acyclic coloring of graphs. Random Structures and Algorithms, 2(3):277-288, 1991.
	4	N. Alon, J. Spencer, and P. Erd6s. The Probabilistic Method. John Wiley &: Sons, New York, 1992.
	5	Takao Asano , Kuniaki Hori , Takao Ono , Tomio Hirata, A Theoretical Framework of Hybrid Approaches to MAX SAT, Proceedings of the 8th International Symposium on Algorithms and Computation, p.153-162, December 17-19, 1997
	6	Takao Asano , David P. Williamson, Improved approximation algorithms for MAX SAT, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.96-105, January 09-11, 2000, San Francisco, California, United States
	7	J. Beck. An algorithmic approach to the Lov~isz local lemma. Random Structures and Algorithms, 2(4):343- 365, 1991.
	8	Andrei Z. Broder , Alan M. Frieze , Eli Upfal, Static and dynamic path selection on expander graphs (preliminary version): a random walk approach, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.531-539, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258646]
	9	Artur Czumaj , Christian Scheideler, Coloring non-uniform hypergraphs: a new algorithmic approach to the general Lovász local lemma, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.30-39, January 09-11, 2000, San Francisco, California, United States
	10	P. Erd6s and L. Lovisz. Problems and results on 3- chromatic hypergraphs and some related questions. In A. Hajnai, R. Rado, and V. S6s, editors, Infinite and Finite Sets (to Paul Erdds on his 60th birthday), pages 609-627. North-Holland, Amsterdam, 1975.
	11	Paul Erdős , Joel Spencer, Lopsided Lova´sz Local Lemma and Latin transversals, Discrete Applied Mathematics, v.30 n.2-3, p.151-154, Feb. 28, 1991
	12	Uriel Feige , Christian Scheideler, Improved bounds for acyclic job shop scheduling (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.624-633, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276878]
	13	Z. Ffiredi and j. Kahn. On the dimensions of ordered sets of bounded degree. Order, 3:15-20, 1986.
	14	Michel X. Goemans , David P. Williamson, New ${\bf \frac{3}{4}}$-Approximation Algorithms for the Maximum Satisfiability Problem, SIAM Journal on Discrete Mathematics, v.7 n.4, p.656-666, Nov. 1994 [doi>10.1137/S0895480192243516]
	15	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]
	16	Leslie Ann Goldberg , Mike Paterson , Aravind Srinivasan , Elizabeth Sweedyk, Better approximation guarantees for job-shop scheduling, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.599-608, January 05-07, 1997, New Orleans, Louisiana, United States
	17	H. Hind, M. Molloy, and B. Reed. Colouring a graph frugally. Combinatorica, 17(4):469-482, 1997.
	18	D. Johnson. Approximation algorithms for combinatorial problems. Journal on Computer and System Science, 9:256-278, 1974.
	19	F. T. Leighton, B. M. Maggs, and S. B. Rao. Packet routing and job-shop scheduling in O(congestion + dilation) steps. Combinatorica, 14(2):167-186, 1994.
	20	F. T. Leighton, B. M. Maggs, and A. W. Richa. Fast algorithms for finding o(congestion q- dilation) packet routing schedules. Technical report, CMU-CS-96-152, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, USA, 1996.
	21	Tom Leighton , Satish Rao , Aravind Srinivasan, New algorithmic aspects of the Local Lemma with applications to routing and partitioning, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.643-652, January 17-19, 1999, Baltimore, Maryland, United States
	22	Chi-Jen Lu, A deterministic approximation algorithm for a minmax integer programming problem, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.663-668, January 17-19, 1999, Baltimore, Maryland, United States
	23	Michael Molloy , Bruce Reed, Further algorithmic aspects of the local lemma, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.524-529, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276866]
	24	Jaikumar Radhakrishnan , Aravind Srinivasan, Improved Bounds and Algorithms for Hypergraph Two-Coloring, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.684, November 08-11, 1998
	25	Prabhakar Raghavan , Clark D. Tompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, v.7 n.4, p.365-374, Dec, 1987 [doi>10.1007/BF02579324]
	26	B. Reed. co, A, and X. Journal of Graph Theory, 27(4):177-212, 1998.
	27	Jeanette P. Schmidt , Alan Siegel , Aravind Srinivasan, Chernoff-Hoeffding Bounds for Applications with Limited Independence, SIAM Journal on Discrete Mathematics, v.8 n.2, p.223-250, May 1995 [doi>10.1137/S089548019223872X]
	28	David B. Shmoys , Clifford Stein , Joel Wein, Improved Approximation Algorithms for Shop Scheduling Problems, SIAM Journal on Computing, v.23 n.3, p.617-632, June 1994 [doi>10.1137/S009753979222676X]
	29	Joel Spencer, Probabilistic methods, Handbook of combinatorics (vol. 2), MIT Press, Cambridge, MA, 1996
	30	Aravind Srinivasan, An extension of the Lovász local lemma, and its applications to integer programming, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.6-15, January 28-30, 1996, Atlanta, Georgia, United States
	31	Mihalis Yannakakis, On the approximation of maximum satisfiability, Journal of Algorithms, v.17 n.3, p.475-502, Nov. 1994

CITED BY 7

	Mohammad R. Salavatipour, A (1 + ε)-approximation algorithm for partitioning hypergraphs using a new algorithmic version of the Lovász Local Lemma, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Mohammad R. Salavatipour, A (1 + ε)-approximation algorithm for partitioning hypergraphs using a new algorithmic version of the Lovász local Lemma, Random Structures & Algorithms, v.25 n.1, p.68-90, August 2004
	Nikhil Bansal , Tracy Kimbrel , Maxim Sviridenko, Job shop scheduling with unit processing times, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Artur Czumaj , Christian Sohler, Testing hypergraph colorability, Theoretical Computer Science, v.331 n.1, p.37-52, 15 February 2005
	Nikhil Bansal , Tracy Kimbrel , Maxim Sviridenko, Job Shop Scheduling with Unit Processing Times, Mathematics of Operations Research, v.31 n.2, p.381-389, February 2006
	Aravind Srinivasan, Improved algorithmic versions of the Lovász Local Lemma, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.611-620, January 20-22, 2008, San Francisco, California
	Viswanath Nagarajan , Maxim Sviridenko, Tight Bounds for Permutation Flow Shop Scheduling, Mathematics of Operations Research, v.34 n.2, p.417-427, May 2009