DIMACS TR: 93-13

Combinatorial Optimization and Computations in the Ring of Polynomials

Author: Alexander I. Barvinok


We reduce a problem of Combinatorial Otimization to a computational problem in the ring of polynomials. As an application, we find new polynomially solvable classes of the Traveling Salesman Problem and the Weighted 3-Packing Problem. In particular, we show that for any fixed norm in a Euclidean space and for any fixed relative error one can compute the length of a longest Hamiltonian contour joining given points in polynomial time. We also design faster PSPACE algorithms for testing Hamiltonian graphs, for the 3-Packing Problem, and the Vertex Disjoint Paths Problem. We prove that the permanent of a matrix can be computed in polynomial time if we fix the rank of the matrix.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-13.ps
DIMACS Home Page