The maximum-feasible-subset scaling conjecture for random K-LSAT
The maximum-feasible-subset scaling conjecture for random K-LSAT
Consider the random K-LSAT linear program with variables and constraints, with all auxiliary variables set to zero. Let be the maximum cardinality of a feasible subset of the constraints , and let be the K-LSAT threshold introduced in the source. Maximum-feasible-subset scaling conjecture. For every , the limit
exists. Moreover, this limit is strictly smaller than one for every . The conjecture is presented as an open analogue of the maximum-SAT conjecture for the generalized linear-programming relaxation.
Sources & referencesView supporting material
Primary source
David Gamarnik, “Linear Phase Transition in Random Linear Constraint Satisfaction Problem”, arXiv:math/0210470 (2003).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.