When Is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem?

DOI10.1137/S0097539792235384zbMath0833.90096OpenAlexW1995289318WikidataQ57401573 ScholiaQ57401573MaRDI QIDQ4842116

Alan M. Frieze, Richard M. Karp, Bruce A. Reed

Publication date: 18 March 1996

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

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

zbMATH Keywords

probabilistic analysisassignment problemasymmetric traveling salesman problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Random graphs (graph-theoretic aspects) (05C80) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Related Items

Unnamed Item, On the relationship between ATSP and the cycle cover problem, Combinação de abordagens GLSP e ATSP para o problema de dimensionamento e sequenciamento de lotes de produção de suplementos para nutrição animal, Hamilton cycles in the union of random permutations, Production setup-sequencing and lot-sizing at an animal nutrition plant through ATSP subtour elimination and patching