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

Voir la notice de l'article provenant de la source Math-Net.Ru

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},
     publisher = {mathdoc},
     volume = {53},
     number = {5},
     year = {2013},
     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
PB  - mathdoc
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
%I mathdoc
%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/