Timeline for Techniques for proving bounds on integrality gap in LP(SDP)
Current License: CC BY-SA 2.5
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 11, 2010 at 7:42 | comment | added | Grigory Yaroslavtsev | 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. | |
| Oct 11, 2010 at 7:36 | comment | added | Grigory Yaroslavtsev | 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. | |
| Oct 11, 2010 at 6:59 | history | answered | Suresh Venkat | CC BY-SA 2.5 |