14
$\begingroup$

Assume we want to refute an unsatisfiable CNF. We can interpret it as an integer program, thus a refutation can be done by applying Lovasz-Schrijver semidefinite cuts ($LS_{+}$ cuts) to its linear relaxation until the polytope is empty.

For a polytope $P$ we consider $N_{+}(P)$ to be the polytope where all possible $LS_{+}$ cuts have been further applied. We can always iterate the operator $N_{+}$ until the resulting polytope is empty. The number of iterations required to reach the empty polytope is called the rank of the polytope.

Since each iteration increases the number of facet of a polynomial factor, a non constant number of iterations is out of question.

In the case of Gomory-Chvátal cuts, the usual PHP formula requires rank $\Omega(\log n)$, but there exists a refutation of polynomial size. Such refutation essentially produces the empty polytope using only a small number of the facets from each iteration.

My question is: does there exist a similar example for $LS_{+}$ cuts, i.e. a case where an short refutation exists but the rank is large?

Update: The following paper shows (among other things) that a tautology with short refutation and linear rank would separate Tree-Like LS+ from general LS+ refutations.

Toniann Pitassi and Nathan Segerlind, "Exponential Lower Bounds and Integrality Gaps for Tree-like Lovasz-Schrijver Procedures", SODA, 2009.

$\endgroup$
  • 1
    $\begingroup$ I assume that LS cuts are Lovasz-Schrijver cuts ? might be helpful to clarify. $\endgroup$ – Suresh Venkat Oct 20 '10 at 17:13
  • 1
    $\begingroup$ So basically you look for a hard tautology (different from PHP) that separates tree-like and dag-like LS+ ? Am I correct ? $\endgroup$ – Iddo Tzameret Oct 21 '10 at 7:42
  • $\begingroup$ I don't know the status of rank size trade-offs in LS+. Of course a positive answer to this question is a step towards the separation you mention. For context: consider PHP under Cutting Planes with Gomory-Chvátal cuts; in this case the short refutation is polynomial size and tree-like while the rank in $\Omega(\log n)$. This is non trivial since usually rank $r$ implies $n^r$ upper bounds, both in GC and LS. Notice that as far as I know even such upper bound is unknown for LS+. My question can be rephrased like: "given that such upper bound exists, it is optimal?". $\endgroup$ – MassimoLauria Oct 21 '10 at 11:09
  • 1
    $\begingroup$ Apparently in SODA 2009, Pitassi and Segerlind proved rank/size trade-off for tree-like and LS and tree-like LS+. Thus Iddo's comment is completely correct. $\endgroup$ – MassimoLauria Oct 29 '10 at 13:08
  • $\begingroup$ Do you want to update your question? (I have added the link to Toni and Nathan's paper.) Also if this is an open problem, we should add the [open-problem] tag. $\endgroup$ – Kaveh Oct 30 '10 at 6:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.