Improved approximations for hard optimization problems via problem instance classification

DOI10.1007/978-3-642-19391-0_1MaRDI QIDQ3003467zbMATH OpenOpenAlexFDO

Authors Juraj Hromkovič, Tobias Mömke, Hans-Joachim Böckenhauer

Publication date 27 May 2011

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

Full work available at URL http://hdl.handle.net/20.500.11850/156326

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• A Modern View on Stability of Approximation
• scientific article; zbMATH DE number 1489999
• scientific article; zbMATH DE number 1775419
• Stability of approximation algorithms or parameterization of the approximation ratio
• Approximability of hard combinatorial optimization problems: an introduction

Cites work

• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1507218 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Algorithms and Data Structures
• An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Bidimensionality: new connections between FPT algorithms and PTASs
• Confronting hardness using a hybrid approach
• Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Fixed-parameter approximation: conceptual framework and approximability results
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Improved approximations for TSP with simple precedence constraints (extended abstract)
• On Computable Numbers, with an Application to the Entscheidungsproblem
• On Parameterized Approximability
• On the Computational Complexity of Algorithms
• On the Hardness of Reoptimization
• On the efficiency of polynomial time approximation schemes
• On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
• P-Complete Approximation Problems
• Paired approximation problems and incompatible inapproximabilities
• Parameterized Approximation Problems
• Parameterized and exact computation. Second international workshop, IWPEC 2006, Zürich, Switzerland, September 13--15, 2006. Proceedings
• Parameterized approximation of dominating set problems
• Parameterized complexity of Vertex Cover variants
• 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
• Reoptimization of Steiner trees: changing the terminal set
• The Steiner problem with edge lengths 1 and 2
• The hardness of approximation: Gap location
• The parameterized approximability of TSP with deadlines
• The steiner problem in graphs

Cited in

(1)

• Approximating a Class of Classification Problems

This page was built for publication: Improved approximations for hard optimization problems via problem instance classification

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