Improved Approximations for Hard Optimization Problems via Problem Instance Classification

DOI10.1007/978-3-642-19391-0_1zbMath1327.68333OpenAlexW96526881MaRDI QIDQ3003467

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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the efficiency of polynomial time approximation schemes
• Performance guarantees for the TSP with a parameterized triangle inequality
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Reoptimization of Steiner trees: changing the terminal set
• Parameterized approximation of dominating set problems
• The Steiner problem with edge lengths 1 and 2
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• The hardness of approximation: Gap location
• Fixed-parameter approximation: conceptual framework and approximability results
• Parameterized and exact computation. Second international workshop, IWPEC 2006, Zürich, Switzerland, September 13--15, 2006. Proceedings
• Parameterized complexity of Vertex Cover variants
• The parameterized approximability of TSP with deadlines
• On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• On Parameterized Approximability
• Parameterized Approximation Problems
• Improved Approximations for TSP with Simple Precedence Constraints
• Confronting hardness using a hybrid approach
• P-Complete Approximation Problems
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
• Fixed-Parameter Tractability and Completeness I: Basic Results
• On the Computational Complexity of Algorithms
• An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables
• On the Hardness of Reoptimization
• The steiner problem in graphs
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Algorithms and Data Structures
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

This page was built for publication: Improved Approximations for Hard Optimization Problems via Problem Instance Classification