The maximum-feasible-subset scaling conjecture for random K-LSAT

Consider the random K-LSAT linear program with nn variables and mm constraints, with all auxiliary variables ψ\psi set to zero. Let N(n,m)N(n,m) be the maximum cardinality of a feasible subset of the constraints CjC_j, and let cKc^*_K be the K-LSAT threshold introduced in the source. Maximum-feasible-subset scaling conjecture. For every c>0c>0, the limit

limnN(n,cn)n\lim_{n\rightarrow\infty}{N(n,cn)\over n}

exists. Moreover, this limit is strictly smaller than one for every c>cKc>c^*_K. 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.