The Traveling Salesman Problem with Many Visits to Few Cities

DOI10.1137/0213007zbMath0529.90091OpenAlexW2086091870MaRDI QIDQ3312037

Christos H. Papadimitriou, Stavros S. Cosmandakis

Publication date: 1984

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0213007

zbMATH Keywords

transportationtraveling salesman problemStirling numbers of the second kindassignment problemStirling's formulafeasible sequenceEdmonds-Karp scaling methodmany visits to few citiesmin-cost max- flow problemminimal Eulerian digraph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Deterministic network models in operations research (90B10) Dynamic programming (90C39)

Related Items (16)

A 3/2-Approximation for the Metric Many-Visits Path TSP ⋮ On the parameterized complexity of the connected flow and many visits TSP problem ⋮ The minimum backlog problem ⋮ High-multiplicity \(N\)-fold IP via configuration LP ⋮ On minimal Eulerian graphs ⋮ Waypoint routing on bounded treewidth graphs ⋮ A polynomial algorithm for an integer quadratic non-separable transportation problem ⋮ Algorithmic meta-theorems for restrictions of treewidth ⋮ New formulation for the high multiplicity asymmetric traveling salesman problem with application to the Chesapeake problem ⋮ Multiplicity and complexity issues in contemporary production scheduling ⋮ On the high multiplicity traveling salesman problem ⋮ Walk on the hypercube with minimum similarities ⋮ High multiplicity asymmetric traveling salesman problem with feedback vertex set and its application to storage/retrieval system ⋮ Many-visits TSP revisited ⋮ Low-complexity algorithms for sequencing jobs with a fixed number of job-classes ⋮ A framework for the complexity of high-multiplicity scheduling problems

This page was built for publication: The Traveling Salesman Problem with Many Visits to Few Cities