Two Algorithmic Results for the Traveling Salesman Problem

DOI10.1287/MOOR.21.1.65zbMath0846.90115OpenAlexW1985376214MaRDI QIDQ4880877

Alexander I. Barvinok

Publication date: 3 October 1996

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.21.1.65

zbMATH Keywords

polynomial time algorithmHamiltonian circuitpermanent of a matrix

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (38)

Rank functions of tropical matrices ⋮ Expressing Polynomials as the Permanent of low rank Square Matrices ⋮ Computing the permanent of (some) complex matrices ⋮ Efficient computation of permanents, with applications to boson sampling and random matrices ⋮ An approximation algorithm for the maximum traveling salesman problem ⋮ A Determinantal Identity for the Permanent of a Rank 2 Matrix ⋮ A hybrid algorithm for multi-homogeneous Bézout number ⋮ Measure concentration in optimization ⋮ A quantization framework for smoothed analysis of Euclidean optimization problems ⋮ The expected characteristic and permanental polynomials of the random Gram matrix ⋮ Inapproximability of positive semidefinite permanents and quantum state tomography ⋮ An efficient tree decomposition method for permanents and mixed discriminants ⋮ Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor ⋮ The complexity of tropical matrix factorization ⋮ On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices ⋮ Detecting matrices of combinatorial rank three ⋮ The factorization of the permanent of a matrix with minimal rank in prime characteristic ⋮ An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents ⋮ How I got to like graph polynomials ⋮ Approximating permanents and hafnians ⋮ Geometric versions of the three-dimensional assignment problem under general norms ⋮ On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries ⋮ On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic ⋮ An extended tree-width notion for directed graphs related to the computation of permanents ⋮ Unnamed Item ⋮ Factoring a band matrix over a semiring ⋮ Algorithms – ESA 2004 ⋮ Tropical lower bounds for extended formulations ⋮ On Hard Instances of Non-Commutative Permanent ⋮ On hard instances of non-commutative permanent ⋮ On the classical complexity of sampling from quantum interference of indistinguishable bosons ⋮ Univariate ideal membership parameterized by rank, degree, and number of generators ⋮ The permanental process ⋮ Tropical lower bound for extended formulations. II. Deficiency graphs of matrices ⋮ THE MAXIMUM TRAVELING SALESMAN PROBLEM ON BANDED MATRICES ⋮ Tropical semimodules of dimension two ⋮ An approximation algorithm with performance guarantees for the maximum traveling salesman problem on special matrices ⋮ On finding a cyclic tour and a vehicle loading plan yielding maximum profit

This page was built for publication: Two Algorithmic Results for the Traveling Salesman Problem