On the Complexity of the Metric TSP under Stability Considerations

DOI10.1007/978-3-642-18381-2_32zbMath1298.90088OpenAlexW1503339058MaRDI QIDQ3075531

Marcel Schöngens, Rastislav Šrámek, Matúš Mihalák, Peter Widmayer

Publication date: 15 February 2011

Published in: SOFSEM 2011: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-18381-2_32

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Unnamed Item ⋮ Data stability in clustering: a closer look ⋮ Robust optimization in the presence of uncertainty: a generic approach ⋮ Unnamed Item ⋮ On perturbation resilience of non-uniform \(k\)-center ⋮ Stability and Recovery for Independence Systems

Cites Work

• Center-based clustering under perturbation stability
• Smoothed analysis of algorithms