REVIEW 1 cited by
Local Search is Better than Random Assignment for Bounded Occurrence Ordering k-CSPs
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Local Search is Better than Random Assignment for Bounded Occurrence Ordering k-CSPs
read the original abstract
We prove that the Bounded Occurrence Ordering k-CSP Problem is not approximation resistant. We give a very simple local search algorithm that always performs better than the random assignment algorithm. Specifically, the expected value of the solution returned by the algorithm is at least Alg > Avg + a(B,k) (Opt - Avg), where "Opt" is the value of the optimal solution; "Avg" is the expected value of the random solution; and a(B,k)=Omega_k(B^{-(k+O(1))} is a parameter depending only on "k" (the arity of the CSP) and "B" (the maximum number of times each variable is used in constraints). The question whether bounded occurrence ordering k-CSPs are approximation resistant was raised by Guruswami and Zhou (APPROX 2012) who recently showed that bounded occurrence 3-CSPs and "monotone" k-CSPs admit a non-trivial approximation.
Forward citations
Cited by 1 Pith paper
-
Strong Refutation of Random Ordering CSPs
Random ordering CSPs with coordinate-degree-d predicates admit poly-time ε-strong refutation above ~n^{d/2}/ε² clauses, with a smooth time-density-ε tradeoff via Kikuchi matrices that is near-optimal under the low-coo...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.