Abstract:
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.
Key words:combinatorial optimization problems, cones of multipowers, tensor extensions of polyhedra.
Fulltext:
PDF file (230 kB)