A reference to techniques for proving that the size of an integrality gap is bounded by some expression for a particular LP(or SDP, but less important) is needed. Also it would be nice to have a reference to a place where techniques for minimizing integrality gaps are described. I am new in the area of integrality gaps, which looks rather huge, so description of classical results is more preferable than that of something hot.
$\begingroup$
$\endgroup$
1
asked Oct 11, 2010 at 5:52
-
$\begingroup$ Your title "Integrality gaps in LP(SDP)" is too general, it is better to be more specific with the title of your question. The title is not a tag, it should state your question, something like: "techniques for proving bounds on integrality gap in LP(SDP)". $\endgroup$– KavehCommented Oct 11, 2010 at 16:45
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
For sake of discussion consider minimization problem with objective function $f(x)$. Off the top of my head I can't think of any one dominant technique for proving integrality gaps. Usually the outline of the proof is the form implied by the definition of integrality gap and the details are problem specific.
For showing that the integrality gap is small (i.e. LP is good) the following proof outline is usual. Use some sort of rounding (often randomized) to construct an integral solution $x'$ with $f(x') \le c\cdot f(x)$ for every LP-feasible $x$ (and for every problem instance). It follows that the integrality gap is at most $c$.
For showing that the integrality gap is large the following outline is usual. Exhibit a problem instance with a cheap LP feasible solution and prove that there is no good integral solution.
-
$\begingroup$ Looks like it should be $f(x') \le c f(x)$, right? $\endgroup$ Commented Oct 12, 2010 at 1:04
-
$\begingroup$ Thanks, the approach you described for proving upper bound on the size of the gap is exactly what I am doing. Constructing $x'$ is not a problem in my case, and then I need to prove the inequality $f(x') \le c f(x)$. This is now done in a problem-specific way, that hardly generalizes to similar problems of the same class, so I was curious if there exists some general machinery for this. $\endgroup$ Commented Oct 12, 2010 at 1:15
-
$\begingroup$ @Grigory: I fixed the bug you reported regarding $x'$ that should be $f(x')$. $\endgroup$ Commented Oct 12, 2010 at 13:42
-
$\begingroup$ to add to Warren's notes, there are increasingly sophisticated (and even dependent) rounding schemes, and even schemes for packing/covering problems where the rounding could break feasibility in a bad way. Depending on what your problem is, there are more advanced references available. $\endgroup$ Commented Oct 12, 2010 at 15:28
$\begingroup$
$\endgroup$
2
This is somewhat heavy machinery for what you want, but there's been a large body of work on techniques for designing ever more refined LPs (SDPs) that get closer and closer to the desired integer program. A good reference that reviews these approaches is by Monique Laurent: A comparison of the Sherali-Adams, Lovasz-Schrijver and Laserre Relaxations for 0-1 programming.
Apart from that, I am not aware of a single good source of references: I assume you've at least perused the relevant chapters in Vijay Vazirani's book ?
answered Oct 11, 2010 at 6:59
-
$\begingroup$ Thank you, your first reference is what I had in mind and tried to avoid, because I would like to have something simpler if possible. $\endgroup$ Commented Oct 11, 2010 at 7:36
-
$\begingroup$ As for Vijay's book, it describes the notion of integrality gap briefly, and then goes to discussion of specific problems, without giving general techniques. I suspect that the notion of integrality gap and relevant results about it can be very different from the results about approximation algorithms, because of the first being a mostly geometric problem. $\endgroup$ Commented Oct 11, 2010 at 7:42