Name
Abstract | ||
|---|---|---|
In this paper we present semidefinite programming (SDP) gap instances for the following variants of the Label-Cover problem, closely related to the Unique Games Conjecture: (i) 2-to-1 Label-Cover; (ii) 2-to-2 Label-Cover; (iii) α-constraint Label-Cover. All of our gap instances have perfect SDP solutions. For alphabet size K, the integral optimal solutions have value: (i) O(1/√logK); (ii) O(1/ logK); (iii) O(1/√logK). Prior to this work, there were no known SDP gap instances for any of these problems with perfect SDP value and integral optimum tending to 0. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-14165-2_52 | ICALP |
Keywords | Field | DocType |
gap instance,integral optimal solution,sdp gap instance,label-cover problem,following variant,unique games conjecture,perfect sdp value,alphabet size k,label-cover variant,constraint label-cover,perfect sdp solution | Discrete mathematics,Combinatorics,Unique games conjecture,Vertex cover,Mathematics,Semidefinite programming,Alphabet | Conference |
Volume | ISSN | ISBN |
6198 | 0302-9743 | 3-642-14164-1 |
Citations | PageRank | References |
2 | 0.37 | 15 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| V. Guruswami | 1 | 3205 | 247.96 |
| Subhash Khot | 2 | 2064 | 112.51 |
| Ryan O'Donnell | 3 | 944 | 72.84 |
| Preyas Popat | 4 | 237 | 10.82 |
| Madhur Tulsiani | 5 | 358 | 24.60 |
| Yi Wu | 6 | 122 | 6.77 |