On the hardness of approximating minimization problems

DOI10.1145/167088.167172zbMath1310.68094OpenAlexW2079473728MaRDI QIDQ5248497

Publication date: 7 May 2015

Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/167088.167172

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (60)

The hardness of approximation: Gap location ⋮ Maximizing the number of unused colors in the vertex coloring problem ⋮ An approximation algorithm for clustering graphs with dominating diametral path ⋮ Lower and upper bounds for long induced paths in 3-connected planar graphs ⋮ Probabilistic proof systems — A survey ⋮ Probabilistically checkable proofs and their consequences for approximation algorithms ⋮ On the hardness of approximating the minimum consistent OBDD problem ⋮ Parallel and sequential approximation of shortest superstrings ⋮ Scheduling of conditional executed jobs on unrelated processors ⋮ A robust model for finding optimal evolutionary tree ⋮ On the longest circuit in an alterable digraph ⋮ Almost optimal set covers in finite VC-dimension ⋮ The complexity of approximating a nonlinear program ⋮ Mutual exclusion scheduling ⋮ The complexity of cover graph recognition for some varieties of finite lattices ⋮ A computationally intractable problem on simplicial complexes ⋮ On chromatic sums and distributed resource allocation ⋮ Selection of relevant features and examples in machine learning ⋮ Time-approximation trade-offs for inapproximable problems ⋮ Bin packing with ``largest in bottom constraint: tighter bounds and generalizations ⋮ An approximation algorithm for 3-Colourability ⋮ $st$-Orientations with Few Transitive Edges ⋮ Colorful graph coloring ⋮ On the difficulty of designing good classifiers ⋮ On the approximability of some degree-constrained subgraph problems ⋮ The approximation of maximum subgraph problems ⋮ Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover ⋮ On the approximation of shortest common supersequences and longest common subsequences ⋮ Approximate solution of NP optimization problems ⋮ Average case analysis of greedy algorithms for optimisation problems on set systems ⋮ Coloring graphs by iterated local search traversing feasible and infeasible solutions ⋮ Approximation algorithms for time constrained scheduling ⋮ Approximate association via dissociation ⋮ On approximating the longest path in a graph ⋮ A series of approximation algorithms for the acyclic directed Steiner tree problem ⋮ A well-characterized approximation problem ⋮ Embedding a novel objective function in a two-phased local search for robust vertex coloring ⋮ Fixed-parameter algorithms for cluster vertex deletion ⋮ Degree-Constrained Subgraph Problems: Hardness and Approximation Results ⋮ Vertex deletion problems on chordal graphs ⋮ On the primer selection problem in polymerase chain reaction experiments ⋮ Simple heuristics for unit disk graphs ⋮ Worst-case performance of approximation algorithms for tool management problems ⋮ An adaptive, multiple restarts neural network algorithm for graph coloring ⋮ Three-quarter approximation for the number of unused colors in graph coloring ⋮ Differential approximation algorithms for some combinatorial optimization problems ⋮ Approximations for subset interconnection designs ⋮ Reconstructing a history of recombinations from a set of sequences ⋮ Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs ⋮ Bicriteria Network Design Problems ⋮ Polynomial time approximation schemes for dense instances of $ \mathcal{NP}$-hard problems ⋮ The minimum-entropy set cover problem ⋮ Vertex Deletion Problems on Chordal Graphs ⋮ Approximation algorithms for general parallel task scheduling ⋮ Local majorities, coalitions and monopolies in graphs: A review ⋮ On the complexity of diagram testing ⋮ The complexity of theory revision ⋮ Randomness in interactive proofs ⋮ Some new results in the complexity of allocation and binding in data path synthesis ⋮ Approximation results for the minimum graph coloring problem

This page was built for publication: On the hardness of approximating minimization problems