A Probabilistic Analysis of Christofides’ Algorithm

DOI10.1007/978-3-642-31155-0_20MaRDI QIDQ2904559zbMATH OpenOpenAlexFDO

Authors Markus Bläser, Konstatinos Panagiotou, B. V. Raghavendra Rao

Publication date 14 August 2012

Published in Algorithm Theory – SWAT 2012 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-31155-0_20

Mathematics Subject Classification ID

Approximation algorithms (68W25) Analysis of algorithms (68W40) Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 4137536
• scientific article; zbMATH DE number 4049028
• scientific article; zbMATH DE number 4047070
• scientific article; zbMATH DE number 1246226
• scientific article; zbMATH DE number 3997543
• On some conditioning results in the probabilistic analysis of algorithms
• The probabilistic analysis of a greedy satisfiability algorithm
• scientific article; zbMATH DE number 1947423
• scientific article; zbMATH DE number 3936510
• A generalized characterization of algorithmic probability

Cited in

(5)

• A probabilistic analysis of the switching algorithm for the Euclidean TSP
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Dynamic algorithms in D. E. Knuth's model: A probabilistic analysis
• scientific article; zbMATH DE number 3869068 (Why is no real title available?)
• A feature-based comparison of local search and the Christofides algorithm for the travelling salesperson problem

This page was built for publication: A Probabilistic Analysis of Christofides’ Algorithm

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