Geodesic
Cones of multipowers and combinatorial optimization problems
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 53 (2013) no. 5, pp. 816-824 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The cone of multipowers is dual to the cone of nonnegative polynomials. The relation of the former cone to combinatorial optimization problems is examined. Tensor extensions of polyhedra of combinatorial optimization problems are used for this purpose. The polyhedron of the MAX-2-CSP problem (optimization version of the two-variable constraint satisfaction problem) of tensor degree $4k$ is shown to be the intersection of the cone of $4k$-multipowers and a suitable affine space. Thus, in contrast to SDP relaxations, the relaxation to a cone of multipowers becomes tight even for an extension of degree 4. 
@article{ZVMMF_2013_53_5_a12,
     author = {M. N. Vyalyi},
     title = {Cones of multipowers and combinatorial optimization problems},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {816--824},
     year = {2013},
     volume = {53},
     number = {5},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2013_53_5_a12/}
}
TY  - JOUR
AU  - M. N. Vyalyi
TI  - Cones of multipowers and combinatorial optimization problems
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2013
SP  - 816
EP  - 824
VL  - 53
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2013_53_5_a12/
LA  - ru
ID  - ZVMMF_2013_53_5_a12
ER  - 
%0 Journal Article
%A M. N. Vyalyi
%T Cones of multipowers and combinatorial optimization problems
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2013
%P 816-824
%V 53
%N 5
%U http://geodesic.mathdoc.fr/item/ZVMMF_2013_53_5_a12/
%G ru
%F ZVMMF_2013_53_5_a12
M. N. Vyalyi. Cones of multipowers and combinatorial optimization problems. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 53 (2013) no. 5, pp. 816-824. http://geodesic.mathdoc.fr/item/ZVMMF_2013_53_5_a12/

[1] Goemans M., Williamson D., “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming”, J. ACM, 42 (1995), 1115–1145 | DOI | MR | Zbl

[2] Lasserre J. B., “An explicit equivalent positive semidefinite program for nonlinear 0–1 programs”, SIAM J. Optimizat., 12:3 (2002), 756–769 | DOI | MR | Zbl

[3] Sherali H. D., Adams W. P., “A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems”, SIAM J. Discrete Math., 3:3 (1990), 411–430 | DOI | MR | Zbl

[4] Lovász L., Schrijver A., “Cones of matrices and setfunctions and 0–1 optimization”, SIAM J. Optimizat., 1:12 (1991), 166–190 | DOI | MR | Zbl

[5] Khot S., “On the power of unique 2-prover 1-round games”, STOC'02, Proc. of the thirty-fourth annual ACM symposium on Theory of computing, ACM, NY, 2002, 767–775 | MR | Zbl

[6] Khot S., Kindler G., Mossel E., O'Donnell R., Optimal inapproximability results for MAX-CUT and Other 2-variable CSPs?, SIAM J. Comput., 37:1 (2007), 319–357 | DOI | MR | Zbl

[7] Håstad J., “Some optimal inapproximability results”, J. ACM, 48 (2001), 798–869 | DOI | MR

[8] Dinur I., “PCP theorem by gap amplification”, Proc. Thirty-Eighth Annual ACM Symposium on Theory of Computing, ACM, NY, 2006, 241–250 | DOI | MR

[9] Khot S., Vishnoi N., “The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into $l_1$”, Proc. 46th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, 2005, 53–62 | DOI

[10] Raghavendra P., Steurer D., “Integrality Gaps for Strong SDP Relaxations of Unique Games”, Proc. 50th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, 2009, 575–585 | MR

[11] Prasolov V. V., Mnogochleny, MTsNMO, M., 2000

[12] Blekherman G., “Nonnegative polynomials and sums of squares”, J. AMS, 25 (2012), 617–635 | MR | Zbl

[13] Sanyal R., Sottile F., Sturmfels B., “Orbitopes”, Mathematika, 57 (2011), 275–314 | DOI | MR | Zbl