Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
type: Item
instance of: scholarly article
title: Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
zbMATH Open document ID: 1094.90036
DOI: 10.1016/S0304-3975(01)00287-0
author: Hans-Joachim Böckenhauer
author: Juraj Hromkovič
author: Ralf Klasing
author: Sebastian Seibert
author: Walter Unger
published in: Theoretical Computer Science
publication date: 2002-08-05T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C31
zbMATH DE Number: 1776344
zbMATH Keywords: Stability of approximation
zbMATH Keywords: Traveling salesman problem
MaRDI profile type: Publication
cites work: On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
cites work: Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
cites work: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
cites work: Q4258216
cites work: Performance guarantees for the TSP with a parameterized triangle inequality
cites work: Q4503938
cites work: Q4293543
cites work: The complexity of theorem-proving procedures
cites work: Q3619797
cites work: Q4198056
cites work: Q3002852
cites work: Q4941164
cites work: Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
cites work: Approximation algorithms for combinatorial problems
cites work: Q3677509
cites work: On the ratio of optimal integral and fractional covers
cites work: Lectures on proof verification and approximation algorithms
cites work: Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
cites work: The Euclidean traveling salesman problem is NP-complete
cites work: Q4298260
Recommended article: Q4503938
Recommended article: Q4496241
Recommended article: Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem
Recommended article: Q4206576
Recommended article: Stability aspects of the traveling salesman problem based on \(k\)-best solutions
Recommended article: On the approximability of the traveling salesman problem (extended abstract)
Recommended article: Q4941164
Recommended article: Differential approximation results for the traveling salesman and related problems
Recommended article: Stability of Approximation in Discrete Optimization
Recommended article: Q3415353
description: scientific article; zbMATH DE number 1776344