Stability of approximation algorithms for hard optimization problems

DOI10.1007/3-540-47849-3_2MaRDI QIDQ4496241zbMATH OpenFDO

Authors Juraj Hromkovič

Publication date 6 June 2001

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-47849-3_2

zbMATH Keywords

hard optimization problemsknapsack problempolynomial-time algorithmstabilitytraveling salesperson problemworst-case complexity

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Complexity and performance of numerical algorithms (65Y20) Transportation, logistics and supply chain management (90B06) Nonlinear programming (90C30) Sensitivity, stability, parametric optimization (90C31)

Recommendations

• Stability of approximation algorithms and the knapsack problem
• Stability of Approximation in Discrete Optimization
• Stability of approximation algorithms or parameterization of the approximation ratio
• A Modern View on Stability of Approximation

Cited in

(17)

• Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
• Reoptimization of the metric deadline TSP
• Are stable instances easy?
• Improved approximations for hard optimization problems via problem instance classification
• Sub-optimality Approximations
• Computational algorithms for finding the radius of stability in problems of choice
• scientific article; zbMATH DE number 4127013 (Why is no real title available?)
• On stability of Oja algorithm
• Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem
• Approximation Algorithms for the Traveling Salesman Problem with Range Condition
• Stability of Approximation in Discrete Optimization
• Stability of approximation algorithms and the knapsack problem
• On the Complexity of the Star p-hub Center Problem with Parameterized Triangle Inequality
• Stability of approximation algorithms or parameterization of the approximation ratio
• On the Hardness of Reoptimization
• Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem
• A Modern View on Stability of Approximation

This page was built for publication: Stability of approximation algorithms for hard optimization problems

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