The hardness of approximation: Gap location

DOI10.1007/BF01202286zbMath0822.68052OpenAlexW3161056635MaRDI QIDQ1332662

Publication date: 1 September 1994

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01202286

zbMATH Keywords

NP-hardness NP-complete optimization problems gap location

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Approximation algorithms for the maximum vertex coverage problem on bounded degree graphs, Improved approximations for max set splitting and max NAE SAT, Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat}, Hard constraint satisfaction problems have hard gaps at location 1, Scheduling with conflicts: Online and offline algorithms, Energy-Efficient Algorithms for Non-preemptive Speed-Scaling, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, Approximability of maximum splitting of k-sets and some other Apx-complete problems, Approximation algorithms for two parallel dedicated machine scheduling with conflict constraints, Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs, Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design, Hardness of \(k\)-vertex-connected subgraph augmentation problem, Combinatorial approximation of maximum k-vertex cover in bipartite graphs within ratio 0.7, New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover, Approximation and Hardness Results for the Maximum Edges in Transitive Closure Problem, Capacitated covering problems in geometric spaces, Between a rock and a hard place: the two-to-one assignment problem, Computing densest \(k\)-subgraph with structural parameters, Complexity and approximation algorithms for two parallel dedicated machine scheduling with conflict constraints, The most vital nodes with respect to independent set and vertex cover, A parameterized approximation scheme for generalized partial vertex cover, An improved algorithm for parallel machine scheduling under additional resource constraints, Unnamed Item, Maximizing coverage while ensuring fairness: a tale of conflicting objectives, Partitioning a weighted partial order, Approximation of satisfactory bisection problems, Parameterized and approximation complexity of \textsc{Partial VC Dimension}, On the cycle augmentation problem: hardness and approximation algorithms, Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures, Improved Approximations for Hard Optimization Problems via Problem Instance Classification, Inapproximability results for combinatorial auctions with submodular utility functions, The path partition problem and related problems in bipartite graphs, Maximizing a submodular function with viability constraints, Exact algorithms for the matrix bid auction, Structure of polynomial-time approximation, Shape rectangularization problems in intensity-modulated radiation therapy, Maximum bipartite flow in networks with adaptive channel width, Inapproximability results for no-wait job shop scheduling., An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance, Lossy kernelization of same-size clustering, Approximating vector scheduling: almost matching upper and lower bounds, Maximum Betweenness Centrality: Approximability and Tractable Cases, Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs, Hardness of approximation for orthogonal rectangle packing and covering problems, Zero knowledge and the chromatic number, Spooky Encryption and Its Applications, On approximation of max-vertex-cover, Multi-dimensional vector assignment problems, Lossy kernelization of same-size clustering, The minimum-entropy set cover problem, Balanced partitions of trees and applications, Hardness results for neural network approximation problems, The generalized assignment problem with minimum quantities

Cites Work