Bridging between 0/1 and linear programming via random walks
From MaRDI portal
Abstract: Under the Strong Exponential Time Hypothesis, an integer linear program with Boolean-valued variables and equations cannot be solved in time for any constant . If the domain of the variables is relaxed to , the associated linear program can of course be solved in polynomial time. In this work, we give a natural algorithmic bridging between these extremes of - and linear programming. Specifically, for any subset (finite union of intervals) containing , we give a random-walk based algorithm with runtime that finds a solution in to any -variable linear program with constraints that is feasible over . Note that as expands from to , the runtime improves smoothly from to polynomial. Taking in our result yields as a corollary a randomized time algorithm for -SAT. While our approach has some high level resemblance to Sch"{o}ning's beautiful algorithm, our general algorithm is based on a more sophisticated random walk that incorporates several new ingredients, such as a multiplicative potential to measure progress, a judicious choice of starting distribution, and a time varying distribution for the evolution of the random walk that is itself computed via an LP at each step (a solution to which is guaranteed based on the minimax theorem). Plugging the LP algorithm into our earlier polymorphic framework yields fast exponential algorithms for any CSP (like -SAT, -in--SAT, NAE -SAT) that admit so-called `threshold partial polymorphisms.'
Recommendations
- Observed lower bounds for random 3-SAT phase transition density using linear programming
- An LP-Designed Algorithm for Constraint Satisfaction
- A Complexity Index for Satisfiability Problems
- A better algorithm for random \(k\)-SAT
- Linear-programming design and analysis of fast algorithms for Max 2-CSP
Cited in
(5)- CNF satisfiability in a subspace and related problems
- Observed lower bounds for random 3-SAT phase transition density using linear programming
- On super strong ETH
- A survey on the fine-grained complexity of constraint satisfaction problems based on partial polymorphisms
- UP-DPC: ultra-scalable parallel density peak clustering
This page was built for publication: Bridging between 0/1 and linear programming via random walks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212799)