Constraint satisfaction, packet routing, and the lovasz local lemma
From MaRDI portal
Publication:5495839
DOI10.1145/2488608.2488696zbMath1293.68168OpenAlexW1988777344MaRDI QIDQ5495839
David G. Harris, Aravind Srinivasan
Publication date: 7 August 2014
Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2488608.2488696
constraint satisfaction problemsLovász local lemmachromatic capacitypacket routingindependent transversal
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
Related Items
Coupled and \(k\)-sided placements: generalizing generalized assignment, A rainbow blow‐up lemma, Scheduling Problems over Network of Machines, Approximation Algorithms for Generalized Path Scheduling, Scheduling problems over a network of machines, Counting Hypergraph Colorings in the Local Lemma Regime, Non-approximability and Polylogarithmic Approximations of the Single-Sink Unsplittable and Confluent Dynamic Flow Problems
