Constraint satisfaction, packet routing, and the lovasz local lemma

摘要: Constraint-satisfaction problems (CSPs) form a basic family of NP-hard optimization that includes satisfiability. Motivated by the sufficient condition for satisfiability SAT formulae is offered Lovasz Local Lemma, we seek such conditions arbitrary CSPs. To this end, identify variable-covering radius--type parameter infeasible configurations given CSP, and also develop an extension Lemma in which many events to be avoided have probabilities arbitrarily close one; these lead general One primary application packet-routing classical Leighton-Maggs-Rao setting, where introduce several additional ideas order prove existence near-optimal schedules; further applications combinatorial are shown.