Non-approximability results for optimization problems on bounded degree instances
From MaRDI portal
Publication:5176001
DOI10.1145/380752.380839zbMath1323.90059WikidataQ29999283 ScholiaQ29999283MaRDI QIDQ5176001
Publication date: 27 February 2015
Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/380752.380839
90C35: Programming involving graphs or networks
68Q25: Analysis of algorithms and problem complexity
90C27: Combinatorial optimization
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Set covering approach for reconstruction of sibling relationships, Hardness of approximate two-level logic minimization and PAC learning with membership queries, Inapproximability of maximal strip recovery, Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs, Approximation hardness of dominating set problems in bounded degree graphs, Independent sets in bounded-degree hypergraphs, Hardness of approximation for non-overlapping local alignments., Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs, Complexity of approximating bounded variants of optimization problems, Vertex cover might be hard to approximate to within \(2 - \varepsilon \), Approximating the online set multicover problems via randomized winnowing, Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons, Inapproximability of b-Matching in k-Uniform Hypergraphs
