Artur Czumaj
Christian Scheideler
- 1.N. Alon. A parallel algorithmic version of the local lemma. Random Structures and Algorithms, 2(4):367- 387, 1991.Google Scholar
Digital Library
- 2.N. Alon, A. Bar-Noy, N. Linial, and D. Peleg. A lower bound for radio broadcast. Journal on Computer and System Science, 43(2):290-298, 1991. Google ScholarDigital Library
- 3.N. Alon, C. McDiarmid, and B. Reed. Acyclic coloring of graphs. Random Structures and Algorithms, 2(3):277-288, 1991.Google ScholarDigital Library
- 4.N. Alon, J. Spencer, and P. Erd6s. The Probabilistic Method. John Wiley &: Sons, New York, 1992.Google Scholar
- 5.T. Asano, K. Hori, T. Ono, and T. Hirata. A theoretical framework of hybrid approaches to MAX SAT. In Proc. of the 8th Syrup. on Algorithms and Computation (ISAAC), pages 153-162, 1997. Google ScholarDigital Library
- 6.T. Asano and D. Williamson. Improved approximation algorithms for MAX SAT. In Proc. of the ilth A CM Syrup. on Discrete Algorithms (SODA), pages 96-105, 2000. Google ScholarDigital Library
- 7.J. Beck. An algorithmic approach to the Lov~isz local lemma. Random Structures and Algorithms, 2(4):343- 365, 1991.Google ScholarDigital Library
- 8.A. Z. Broder, A. M. Frieze, and E. Upfal. Static and dynamic path selection on expander graphs: A random walk approach. In Proc. of the 29th A CM Syrup. on Theory of Computing (STOC), pages 531-539, 1997. Google ScholarDigital Library
- 9.A. Czumaj and C. Scheideler. Coloring non-uniform hypergraphs: A new algorithmic approach to the general Lovasz local lemma. In Proc. of the 11th A CM Syrup. on Discrete Algorithms (SODA), pages 30-39, 2000. Google ScholarDigital Library
- 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.Google Scholar
- 11.P. Erd6s and J. Spencer. Lopsided Lovisz local lemma and latin transversals. Discrete Applied Mathematics, 30:151-154, 1991. Google ScholarDigital Library
- 12.U. Feige and C. Scheideler. Improved bounds for acyclic job shop scheduling. In Proc. of the 30th A CM Syrup. on Theory of Computing (STOC), pages 624-633, 1998. Google ScholarDigital Library
- 13.Z. Ffiredi and j. Kahn. On the dimensions of ordered sets of bounded degree. Order, 3:15-20, 1986.Google ScholarCross Ref
- 14.M. Goemans and D. Williamson. New 3/4- approximation algorithms for the maximum satisfiability problem. SiAM Journal on Computing, 7:656-666, 1994. Google ScholarDigital Library
- 15.M. Goemans and D. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42:1115-1145, 1995. Google ScholarDigital Library
- 16.L. A. Goldberg, M. Paterson, A. Srinivasan, and E. Sweedyk. Better approximation guarantees for jobshop scheduling. In Proc. of the 8th A CM Syrup. on Discrete Algorithms (SODA), pages 599-608, 1997. Google ScholarDigital Library
- 17.H. Hind, M. Molloy, and B. Reed. Colouring a graph frugally. Combinatorica, 17(4):469-482, 1997.Google ScholarCross Ref
- 18.D. Johnson. Approximation algorithms for combinatorial problems. Journal on Computer and System Science, 9:256-278, 1974.Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google Scholar
- 21.T. Leighton, S. Rao, and A. Srinivasan. New algorithmic aspects of the Local Lemma with applications to routing and partitioning. In Proc. of the l Oth A CM Syrup. on Discrete Algorithms (SODA), pages 643-652, 1999. Google ScholarDigital Library
- 22.C.-J. Lu. A deterministic approximation algorithm for a minmax integer programming problem. In Proc. of the l Oth A CM Syrup. on Discrete Algorithms (SODA), pages 663-668, 1999. Google ScholarDigital Library
- 23.M. Molloy and B. Reed. Further algorithmic aspects of the local lemma. In Proc. of the 30th A CM Syrup. on Theory of Computing (STOC), pages 524-529, 1998. Google ScholarDigital Library
- 24.J. Radhakrishnan and A. Srinivasan. Improved bounds and algorithms for hypergraph two-coloring. In Proc. of the 39th IEEE Syrup. on Foundations of Computer Science (FOCS), pages 684-693, 1998. Google ScholarDigital Library
- 25.P. Raghavan and C. Thompson. Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica, 7:365-374, 1987. Google ScholarDigital Library
- 26.B. Reed. co, A, and X. Journal of Graph Theory, 27(4):177-212, 1998. Google ScholarDigital Library
- 27.J. Schmidt, A. Siegel, and A. Srinivasan. Chernoff- Hoeffding bounds for applications with limited independence. SIAM Journal on Discrete Mathematics, 8(2):223-250, 1995. Google ScholarDigital Library
- 28.D. Shmoys, C. Stein, and J. Wein. Improved approximation algorithms for shop scheduling problems. SIAM Journal on Computing, 23(3):617-632, 1994. Google ScholarDigital Library
- 29.J. Spencer. Probabilistic methods. In R. Graham, M. GrStschel, and L. Lovisz, editors, Handbook of Combinatorics, chapter 33. Elsevier Science, Amsterdam, 1995. Google ScholarDigital Library
- 30.A. Srinivasan. An extension of the Lovisz local lemma, and its applications to integer programming, in Proc. of the 7th A CM Syrup. on Discrete Algorithms (SODA), pages 6-15, 1996. Google ScholarDigital Library
- 31.M. Yannakakis. On the approximation of maximum satisfiability. Journal of Algorithms, 17:475-502, 1994. Google ScholarDigital Library
Index Terms
- A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems (extended abstract)
Recommendations
A constructive proof of the general lovász local lemma
The Lovász Local Lemma discovered by Erdős and Lovász in 1975 is a powerful tool to non-constructively prove the existence of combinatorial objects meeting a prescribed collection of criteria. In 1991, József Beck was the first to demonstrate that a ...
Deterministic algorithms for the Lovász Local Lemma
SODA '10: Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithmsThe Lovász Local Lemma [5] (LLL) is a powerful result in probability theory that states that the probability that none of a set of bad events happens is nonzero if the probability of each event is small compared to the number of events that depend on ...
A Kolmogorov complexity proof of the Lovász Local Lemma for satisfiability
The Lovasz Local Lemma provides a syntactic property that a Boolean formula is satisifiable. Moser and Tardos came up with a constructive proof of the lemma, i.e. the proof gives a method to actually construct a satisfying assignment. In this paper, we ...
Comments