On the hardness of approximating minimization problems

DOI10.1145/185675.306789zbMath0814.68064OpenAlexW2059453880WikidataQ55966575 ScholiaQ55966575MaRDI QIDQ4323730

Mihalis Yannakakis, Carstent Lund

Publication date: 20 February 1995

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

minimization problemsgraph coloringset covering

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Coloring Jacobians revisited: a new algorithm for star and~acyclic bicoloring, Sparse Graphs and an Augmentation Problem, Unnamed Item, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation, On the connectivity preserving minimum cut problem, Known Algorithms for Edge Clique Cover are Probably Optimal, Simple decentralized graph coloring, The graph motif problem parameterized by the structure of the input graph, A multiple testing method for hypotheses structured in a directed acyclic graph, Compact Flow Diagrams for State Sequences, Clique Cover and Graph Separation, Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem, Polynomial Kernel for Interval Vertex Deletion, Structure in approximation classes, The Hardness of Approximating Poset Dimension, Exact algorithms and hardness results for geometric red-blue hitting set problem, Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems, On the structure of the set of panchromatic colorings of a random hypergraph, Observation routes and external watchman routes, Approximating minimum keys and optimal substructure screens, From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More, A dynamic programming algorithm for the \(k\)-haplotyping problem, The Complexity of Complexity, How to guard a graph against tree moves, Parallel Repetition of Two-Prover One-Round Games: An Exposition, MAXIMAL INDEPENDENT SET, WEAKLY-CONNECTED DOMINATING SET, AND INDUCED SPANNERS IN WIRELESS AD HOC NETWORKS, A SIMPLE HEURISTIC FOR MINIMUM CONNECTED DOMINATING SET IN GRAPHS, The Constant Inapproximability of the Parameterized Dominating Set Problem, Coresets for the Nearest-Neighbor Rule, Fractional Set Cover in the Streaming Model., CHECKCOL: improved local search for graph coloring, The Optimal Design of Low-Latency Virtual Backbones, Constrained target controllability of complex networks, Quadratic vertex kernel for split vertex deletion, Minimum propositional proof length is NP-hard to linearly approximate, Algorithms for the line-constrained disk coverage and related problems, Helly-type theorems for approximate covering, Safe Lower Bounds for Graph Coloring, MULTI COVER OF A POLYGON MINIMIZING THE SUM OF AREAS, Fractionally total colouring \(G_{n,p}\), Minimum cost source location problems with flow requirements, Algorithms for the line-constrained disk coverage and related problems, Minimizing number of wavelengths in multicast routing trees in WDM networks, On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem, Semi-Definite positive Programming Relaxations for Graph K_n-Coloring in Frequency Assignment, EFFICIENT DISTRIBUTED ALGORITHMS FOR TOPOLOGY CONTROL PROBLEM WITH SHORTEST PATH CONSTRAINTS, LOCAL CONSTRUCTION AND COLORING OF SPANNERS OF LOCATION AWARE UNIT DISK GRAPHS, On the complexity of resilient network design, Unnamed Item, Conflict free version of covering problems on graphs: classical and parameterized, Hardness and methods to solve CLIQUE, Approximating \(k\)-forest with resource augmentation: a primal-dual approach, An approximation algorithm for the partial vertex cover problem in hypergraphs, The set covering problem revisited: an empirical study of the value of dual information, Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes, Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP, Unnamed Item, Approximation Algorithms for Minimum Chain Vertex Deletion, Multi Cover of a Polygon Minimizing the Sum of Areas, On the tractability of covering a graph with 2-clubs, On the Approximability of Some Haplotyping Problems, Hardness of approximate two-level logic minimization and PAC learning with membership queries, Distributed set cover approximation: Primal-dual with optimal locality, A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem, Fuzzy Clustering based on Coverings, On Interference Graphs, A Characterization of Graphs with Fractional Total Chromatic Number Equal to, Approximation of a batch consolidation problem, Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem, On the hardness of approximating the min-hack problem, Nearly Optimal NP-Hardness of Unique Coverage, Complexities of Some Problems Related to Synchronizing, Non-Synchronizing and Monotonic Automata, Approximability issues of guarding a set of segments, Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons, Efficiently computing succinct trade-off curves, On approximate learning by multi-layered feedforward circuits, Minimum Power Dominating Sets of Random Cubic Graphs, Towards optimal lower bounds for clique and chromatic number., Max-min fair rate allocation and routing in energy harvesting networks: algorithmic analysis, Theoretical complexity of grid cover problems used in radar applications, (Total) vector domination for graphs with bounded branchwidth, A note on approximating graph genus, Hop constrained Steiner trees with multiple root nodes, Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank, An overview of graph covering and partitioning, Approximability of identifying codes and locating-dominating codes, Approximability of maximum splitting of k-sets and some other Apx-complete problems, On proving that a graph has no large clique: A connection with Ramsey theory, Complexity and approximation results on the shared transportation problem, The hardness of approximate optima in lattices, codes, and systems of linear equations, Set covering with almost consecutive ones property, Sparse approximation is provably hard under coherent dictionaries, Improved approximation algorithms for the spanning star forest problem, The complexity and approximability of finding maximum feasible subsystems of linear relations, Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms, Probabilistic distributed algorithms for energy efficient routing and tracking in wireless sensor networks, Approximately dominating representatives, Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function, On the intractability landscape of digraph intersection representations, Rounding algorithms for covering problems, Hardness results and spectral techniques for combinatorial problems on circulant graphs, Statistical mechanics of the minimum dominating set problem, Laplacian distribution and domination, Heuristic algorithms in computational molecular biology, Scheduling large-scale micro/nano biochemical testing: Exact and heuristic algorithms, Approximate strong separation with application in fractional graph coloring and preemptive scheduling., Approximation and hardness results for label cut and related problems, Approximating covering integer programs with multiplicity constraints, Approximation algorithms for a geometric set cover problem, On the approximability of covering points by lines and related problems, On good algorithms for determining unsatisfiability of propositional formulas, Maximum-weight stable sets and safe lower bounds for graph coloring, Hardness of approximating the closest vector problem with pre-processing, On the robust hardness of Gröbner basis computation, Improved non-approximability results for minimum vertex cover with density constraints, PCP characterizations of NP: toward a polynomially-small error-probability, A survey on the structure of approximation classes, Evaluation of reliability bounds by set covering models., Hardness results for covering arrays avoiding forbidden edges and error-locating arrays, Using error decay prediction to overcome practical issues of deep active learning for named entity recognition, How to guard a graph?, On the computational complexity of the minimum committee problem, Independent dominating set problem revisited, Efficient sensor network design for continuous monitoring of moving objects, Polynomial cases for the vertex coloring problem, On the geometric red-blue set cover problem, On the kernel size of clique cover reductions for random intersection graphs, Inapproximability results for combinatorial auctions with submodular utility functions, Easy capacitated facility location problems, with connections to lot-sizing, Complete partitions of graphs, Primal-dual approximation algorithms for integral flow and multicut in trees, Homomorphism bounds and edge-colourings of \(K_{4}\)-minor-free graphs, Finding the maximal adversary structure from any given access structure, Approximation algorithm for coloring of dotted interval graphs, Restricted parameter range promise set cover problems are easy, Consecutive block minimization is 1.5-approximable, Surrogate constraint normalization for the set covering problem, Improved approximation algorithms for capacitated facility location problems, Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring, Conversion of coloring algorithms into maximum weight independent set algorithms, On the complexity of directed intersection representation of DAGs, Domination in graphs with bounded propagation: Algorithms, formulations and hardness results, Improved algorithm to determine 3-colorability of graphs with minimum degree at least 7, Rank reduction of oriented graphs by vertex and edge deletions, Large-scale clique cover of real-world networks, Bounds on upper transversals in hypergraphs, Computational complexity of the minimum committee problem and related problems, Approximation of the \(k\)-batch consolidation problem, A randomised approximation algorithm for the hitting set problem, On the domination search number, Hierarchically specified unit disk graphs, Notes on tree- and path-chromatic number, An application of the greedy heuristic of set cover to traffic checks, All structured programs have small tree width and good register allocation, Approximate hierarchical facility location and applications to the bounded depth Steiner tree and range assignment problems, On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems, On the hardness of approximating shortest integer relations among rational numbers, Zero knowledge and the chromatic number, On the hardness of approximating label-cover, Some APX-completeness results for cubic graphs, A note on the approximability of the toughness of graphs, Computing a small agreeable set of indivisible items, A note on the subadditive network design problem, Alarm placement in systems with fault propagation, Covering arrays avoiding forbidden edges, On the complexity of SNP block partitioning under the perfect phylogeny model, Approximating the weight of shallow Steiner trees, A polynomial kernel for bipartite permutation vertex deletion, Generalized submodular cover problems and applications, Graph imperfection. II, Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs, Improved methods for approximating node weighted Steiner trees and connected dominating sets., Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems., On subexponential and FPT-time inapproximability, Faster parameterized algorithms for deletion to split graphs, Tight bounds on subexponential time approximation of set cover and related problems, Sparse graphs and an augmentation problem