New algorithmic aspects of the Local Lemma with applications to routing and partitioning

No abstract is available for this paper.

• Publication year

  2002

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  2002-02-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/S0097539700379760
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Edge-disjoint paths in expander graphs

  2000cited by this paper
• Optimal construction of edge-disjoint paths in random regular graphs

  2000cited by this paper
• A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems (extended abstract)

  2000cited by this paper
• A New Algorithmic Approach to the General Lovász Local Lemma with Applications to Scheduling and Satisfiability Problems

  2000cited by this paper
• Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach

  1999cited by this paper
• A deterministic approximation algorithm for a minmax integer programming problem

  1999cited by this paper
• Deterministic Hypergraph Coloring and Its Applications

  1998cited by this paper
• Disjoint Paths in Expander Graphs via Random Walks: A Short Survey

  1998cited by this paper
• Multicommodity flow and circuit switching

  1998cited by this paper
• The Probabilistic Method

  1998cited by this paper
• Further algorithmic aspects of the local lemma

  1998cited by this paper
• An efficient algorithm for the vertex-disjoint paths problem in random graphs

  1996cited by this paper
• An extension of the Lovász local lemma, and its applications to integer programming

  1996cited by this paper
• Short paths in expander graphs

  1996cited by this paper
• Approximation algorithms for disjoint paths problems

  1996cited by this paper
• Chernoff-Hoeffding bounds for applications with limited independence

  1995cited by this paper
• Circuit Switching: a Multicommodity Ow Based Approach

  1995cited by this paper
• Randomized algorithms

  1995cited by this paper
• Probability Inequalities for Sums of Bounded Random Variables

  1994cited by this paper
• Optimal construction of edge-disjoint paths in random graphs

  1994cited by this paper
• On the complexity of the disjoint paths problem

  1993cited by this paper
• The String Chromatic Number of a Graph

  1992cited by this paper
• A parallel algorithmic version of the local lemma

  1991influential reference
• An Algorithmic Approach to the Lovász Local Lemma. I

  1991cited by this paper
• Homotopic routing methods

  1990cited by this paper
• On-line algorithms for path selection in a nonblocking network

  1990cited by this paper
• An O(logN) deterministic packet routing scheme

  1989cited by this paper
• An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms

  1988cited by this paper
• Explicit construction of linear sized tolerant networks

  1988cited by this paper
• Ten lectures on the probabilistic method

  1987cited by this paper
• Efficient Parallel Algorithms for Edge Coloring Problems

  1987cited by this paper
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs

  1987cited by this paper
• Assessment of speech intelligibility in five south-eastern Bantu languages: critical considerations.

  1986cited by this paper
• Probabilistic construction of deterministic algorithms: Approximating packing integer programs

  1986cited by this paper
• The art of computer programming

  1983cited by this paper
• On Odd Cuts and Plane Multicommodity Flows

  1981cited by this paper
• Ramanujan Graphs

  1965cited by this paper
• Probability inequalities for sum of bounded random variables

  1963cited by this paper
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

  1952cited by this paper
• Problems and Results on 3-chromatic Hypergraphs and Some Related Questions

  year unknowncited by this paper

• Edge-disjoint paths in expanders: online with removals

  2023influential citation
• D S ] 5 A ug 2 01 9 Algorithms to Approximate Column-Sparse Packing Problems ∗

  2019cites this paper
• D S ] 1 4 A pr 2 01 8 Partial resampling to approximate covering integer programs ∗

  2018cites this paper
• Block-Selection Rounding and Applications∗

  2018cites this paper
• Algorithms to Approximate Column-sparse Packing Problems

  2017cites this paper
• A pr 2 01 7 Partial resampling to approximate covering integer programs ∗

  2017cites this paper
• Dependent randomized rounding for clustering and partition systems with knapsack constraints

  2017cites this paper
• Symmetric Randomized Dependent Rounding

  2017cites this paper
• Dependent rounding for knapsack/partition constraints and facility location

  2017cites this paper
• Distributed MST and Routing in Almost Mixing Time

  2017cites this paper
• Approximation-Friendly Discrepancy Rounding

  2015cites this paper
• Partial resampling to approximate covering integer programs †

  2015cites this paper
• The Moser-Tardos Framework with Partial Resampling

  2013influential citation
• Constraint satisfaction, packet routing, and the lovasz local lemma

  2013cites this paper
• Approximation Algorithms for Throughput Maximization in Wireless Networks With Delay Constraints

  2011influential citation
• Lecture: New Constructive Aspects of the Lov asz Local Lemma, and their Applications | June 15, 2011

  2011cites this paper
• Randomized Pipage Rounding for Matroid Polytopes and Applications

  2009cites this paper
• Dependent Randomized Rounding for Matroid Polytopes and Applications

  2009cites this paper
• Conflict-Free Colourings of Graphs and Hypergraphs

  2009influential citation
• Fast Resource Sharing in

  2009cites this paper
• The fractional congestion bound for efficient edge disjoint routing

  2008influential citation
• An algorithmic Friedman{Pippenger theorem on tree embeddings and applications

  2008cites this paper
• 3-dimensional Routing

  2007cites this paper
• Polylogarithmic Independence Can Fool DNF Formulas

  2007cites this paper
• Finding Disjoint Paths in Expanders Deterministically and Online

  2007cites this paper
• Routing vertex disjoint Steiner-trees in a cubic grid and connections to VLSI

  2007cites this paper
• Single-Path Routing of Time-varying Traffic

  2006cites this paper
• The Santa Claus problem

  2006cites this paper
• An algorithmic Friedman--Pippenger theorem on tree embeddings and applications to routing

  2006influential citation
• The Lovász-Local-Lemma and Scheduling

  2006cites this paper
• The Santa Claus Problem (Extended Abstract)

  2006cites this paper
• CAM04-6: Single-Path Routing of Time-varying Traffic

  2006cites this paper
• 3-dimensional Channel Routing

  2005cites this paper
• Near-Optimum Global Routing with Coupling, Delay Bounds, and Power Consumption

  2004cites this paper
• AN ALGORITHMIC FRIEDMAN–PIPPENGER THEOREM ON TREE EMBEDDINGS (PRELIMINARY VERSION)

  2004cites this paper
• Models, Complexity and Algorithms for the Design of Multi-fiber WDM Networks

  2003cites this paper
• A Gambling Game Arising in the Analysis of Adaptive Randomized Rounding

  2003cites this paper
• Dependent rounding in bipartite graphs

  2002cites this paper
• On Constrained Hypergraph Coloring and Scheduling

  2002influential citation
• Discrete and Computational Geometry

  2001cites this paper
• Arc-disjoint paths in expander digraphs

  2001cites this paper
• A recursive algorithm of obstacles clustering for reducing complexity of collision detection in 2D environment

  2001cites this paper
• Derandomization in Combinatorial Optimization

  2001cites this paper
• Almost optimal permutation routing on hypercubes

  2001cites this paper
• Optimal construction of edge-disjoint paths in random regular graphs

  2000cites this paper
• Coloring non-uniform hypergraphs: a new algorithmic approach to the general Lovász local lemma

  2000cites this paper
• A New Algorithmic Approach to the General Lovász Local Lemma with Applications to Scheduling and Satisfiability Problems

  2000influential citation
• An Algorithmic Approach to the General Lovász Local Lemma with Applications to Scheduling and Satisfiability Problems ∗ ( Technical Report )

  2000influential citation
• 3-Dimensional Single Active Layer Routing

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

  2000cites this paper
• A deterministic approximation algorithm for a minmax integer programming problem

  1999influential citation
• Splitting an Expander Graph

  1999cites this paper
• Approximation algorithms via randomized rounding : a survey

  1999influential citation
• Disjoint Paths in Expander Graphs via Random Walks: A Short Survey

  1998cites this paper
• Deterministic Hypergraph Coloring and Its Applications

  1998influential citation
• Critical Resource Sharing for Cooperation in Complex Systems Efficient Access to Optical Bandwidth Routing and Grooming in Wdm Networks: State-of-the-art Survey

  year unknowncites this paper
• Better Multi-dimesional Bin Packing in Special Cases

  year unknowncites this paper
• Combinatorial Algorithms in VLSI Routing

  year unknowncites this paper