On the hardness of approximating minimization problems
From MaRDI portal
Publication:4323730
DOI10.1145/185675.306789zbMath0814.68064DBLPjournals/jacm/LundY94OpenAlexW2059453880WikidataQ55966575 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
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 (only showing first 100 items - show all)
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 Kn-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
This page was built for publication: On the hardness of approximating minimization problems
