<p>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 href="http://homepages.cwi.nl/~monique/files/lasserrefinal.ps">A comparison of the Sherali-Adams, Lovasz-Schrijver and Laserre Relaxations for 0-1 programming</a>. </p>

<p>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 <a href="http://books.google.com/books?id=EILqAmzKgYIC&amp;printsec=frontcover&amp;dq=approximation+algorithms&amp;source=bl&amp;ots=XjbYJLWW8-&amp;sig=t2rHPHeRiQo8QY7vNraCcKa8o4g&amp;hl=en&amp;ei=j7WyTPXfOY2usAOokLmrAQ&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=3&amp;ved=0CDIQ6AEwAg#v=onepage&amp;q&amp;f=false">Vijay Vazirani's book</a> ? </p>

CC BY-SA 2.5
2010-10-11T07:36:48.450Z
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.
Grigory Yaroslavtsev
CC BY-SA 2.5
2010-10-11T07:42:51.723Z
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.
Grigory Yaroslavtsev
CC BY-SA 2.5
2010-10-11T06:59:26.297Z
2010-10-11T06:59:26.297Z
Suresh Venkat
<p>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.</p>

<p>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$.</p>

<p>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.</p>

CC BY-SA 2.5
2010-10-12T01:04:32.087Z
Looks like it should be $f(x') \le c f(x)$, right?
Grigory Yaroslavtsev
CC BY-SA 2.5
2010-10-12T01:15:59.283Z
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.
Grigory Yaroslavtsev
CC BY-SA 2.5
2010-10-12T13:42:13.913Z
@Grigory: I fixed the bug you reported regarding $x'$ that should be $f(x')$.
Warren Schudy
CC BY-SA 2.5
2010-10-12T15:28:05.453Z
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.
Suresh Venkat
CC BY-SA 2.5
2010-10-11T16:03:32.757Z
2010-10-12T13:41:08.283Z
2010-10-12T13:41:08.283Z
Warren Schudy
<p>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.</p>

CC BY-SA 2.5
2010-10-11T16:45:23.167Z
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)".
Kaveh
<ds.algorithms><reference-request><linear-programming><semidefinite-programming><integrality-gap>
Techniques for proving bounds on integrality gap in LP(SDP)
Grigory Yaroslavtsev
# Techniques for proving bounds on integrality gap in LP(SDP)

(Asked by: username_0 on 2010-10-11)

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.

**Tags:** ds.algorithms, reference-request, linear-programming, semidefinite-programming, integrality-gap

> **Comments:**
> **username_1**: 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)".  

---

## 2 answers

### Answer by username_3 on 2010-10-11. Score: 8 | Accepted answer

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.

> **Comments:**
> **username_0**: Looks like it should be $f(x') \le c f(x)$, right?  
> **username_0**: 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.  
> **username_3**: @Grigory: I fixed the bug you reported regarding $x'$ that should be $f(x')$.  
> **username_2**: 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.  

---

### Answer by username_2 on 2010-10-11. Score: 8

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](http://homepages.cwi.nl/~monique/files/lasserrefinal.ps).

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](http://books.google.com/books?id=EILqAmzKgYIC&printsec=frontcover&dq=approximation+algorithms&source=bl&ots=XjbYJLWW8-&sig=t2rHPHeRiQo8QY7vNraCcKa8o4g&hl=en&ei=j7WyTPXfOY2usAOokLmrAQ&sa=X&oi=book_result&ct=result&resnum=3&ved=0CDIQ6AEwAg#v=onepage&q&f=false) ?

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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.  

---

