A Modern View on Stability of Approximation

DOI10.1007/978-3-319-98355-4_22MaRDI QIDQ6163638zbMATH OpenFDO

Authors Ralf Klasing, Tobias Mömke

Publication date 30 June 2023

Published in Adventures Between Lower Bounds and Higher Altitudes (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-98355-4_22

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Recommendations

• Stability of approximation algorithms or parameterization of the approximation ratio
• Stability of Approximation in Discrete Optimization
• scientific article; zbMATH DE number 1489999
• Publication:4206576
• scientific article; zbMATH DE number 1408349

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
• A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
• A robust and optimal online algorithm for minimum metric bipartite matching
• Algorithmics -- is there hope for a unified theory? (Invited talk)
• An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality
• Approximability and inapproximability of the star p-hub center problem with parameterized triangle inequality
• Approximating total flow time on parallel machines
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Approximation algorithms for the TSP with sharpened triangle inequality
• Approximation schemes for NP-hard geometric optimization problems: a survey
• Bypassing the embedding
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Fundamentals of parameterized complexity
• Geometric algorithms and combinatorial optimization
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• scientific article; zbMATH DE number 3769624 (Why is no real title available?)
• scientific article; zbMATH DE number 1500530 (Why is no real title available?)
• scientific article; zbMATH DE number 1559527 (Why is no real title available?)
• scientific article; zbMATH DE number 1775394 (Why is no real title available?)
• scientific article; zbMATH DE number 1408349 (Why is no real title available?)
• Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
• Introduction to algorithms.
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Maximum Scatter TSP in Doubling Metrics
• Nearest neighbor queries in metric spaces
• On 3-connected graphs of path-width at most three
• On k-connectivity problems with sharpened triangle inequality
• On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality
• On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
• Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
• Performance guarantees for the TSP with a parameterized triangle inequality
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Stability of Approximation in Discrete Optimization
• The approximability of the \(p\)-hub center problem with parameterized triangle inequality
• The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
• Theoretical computer science. Introduction to automata, computability, complexity, algorithmics, randomization, communication, and cryptography.
• Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
• When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree

Cited in

(10)

• From symmetry to asymmetry: generalizing TSP approximations by parametrization
• On the approximability of the single allocation \(p\)-hub center problem with parameterized triangle inequality
• Approximation algorithms for the \(p\)-hub center routing problem in parameterized metric graphs
• Are stable instances easy?
• Improved approximations for hard optimization problems via problem instance classification
• scientific article; zbMATH DE number 1489999 (Why is no real title available?)
• Stability of Approximation in Discrete Optimization
• Stability of approximation algorithms or parameterization of the approximation ratio
• From symmetry to asymmetry: generalizing TSP approximations by parametrization
• On the hardness and approximation of the densest k-subgraph problem in parameterized metric graphs

This page was built for publication: A Modern View on Stability of Approximation

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