The Probabilistic Relationship Between the Assignment and Asymmetric Traveling Salesman Problems

DOI10.1137/S0097539701391518MaRDI QIDQ5422494zbMATH OpenOpenAlexWikidataFDO

Authors Gregory B. Sorkin, Alan Frieze

Publication date 22 October 2007

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

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

zbMATH Keywords

alternating pathAssignment problemasymmetric traveling salesman problemaverage-case analysis of algorithmscycle covermatchingnear-permutation digraphpatching heuristicpermutation digraphrandom assignment problem

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Combinatorial optimization (90C27)

Recommendations

• The probabilistic relationship between the assignment and asymmetric traveling salesman problems.
• When Is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem?
• An \(O(\log n/ \log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
• scientific article; zbMATH DE number 1833413
• The Probabilistic Analysis of a Heuristic for the Assignment Problem

Cited in

(13)

• Typical values of extremal-weight combinatorial structures with independent symmetric weights
• A cutting plane method for risk-constrained traveling salesman problem with random arc costs
• Probabilistic analysis of bipartite traveling salesman problems
• The probabilistic relationship between the assignment and asymmetric traveling salesman problems.
• Probabilistic Analysis of Assignment Ranking: The Traveling Salesman Problems
• scientific article; zbMATH DE number 1833413 (Why is no real title available?)
• scientific article; zbMATH DE number 2118621 (Why is no real title available?)
• When Is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem?
• The cost of strategy-proofness in school choice
• Solving a random asymmetric TSP exactly in quasi-polynomial time w.h.p.
• Smoothed analysis of deterministic discounted and Mean-payoff games
• Hamilton cycles in random digraphs with minimum degree at least one
• Random assignment problems

This page was built for publication: The Probabilistic Relationship Between the Assignment and Asymmetric Traveling Salesman Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5422494)