DIMACS TR: 93-13
Combinatorial Optimization and Computations in the Ring of Polynomials
Author: Alexander I. Barvinok
ABSTRACT
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