Non-approximability results for optimization problems on bounded degree instances
From MaRDI portal
Publication:5176001
DOI10.1145/380752.380839zbMath1323.90059OpenAlexW2001663593WikidataQ29999283 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
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
On regularity of Max-CSPs and Min-CSPs, Tandem Duplications, Segmental Duplications and Deletions, and Their Applications, Complexity of approximating bounded variants of optimization problems, Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs, Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces, Primal-Dual Algorithms for Precedence Constrained Covering Problems, Deterministic versus randomized adaptive test cover, Learning in auctions: regret is hard, envy is easy, Optimal item pricing in online combinatorial auctions, Partial Resampling to Approximate Covering Integer Programs, Primal-dual algorithms for precedence constrained covering problems, Approximating weighted neighborhood independent sets, Extension of some edge graph problems: standard, parameterized and approximation complexity, Technical Note—Online Hypergraph Matching with Delays, On the configuration LP for maximum budgeted allocation, Clustering in Hypergraphs to Minimize Average Edge Service Time, Complexity of majority monopoly and signed domination problems, Designing menus of contracts efficiently: the power of randomization, Randomized scheduling algorithm for queueing networks, Approximability of sparse integer programs, Scheduling to minimize gaps and power consumption, Donation center location problem, Approximating vertex cover in dense hypergraphs, Hardness of approximation for non-overlapping local alignments., Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs, Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs, Vertex cover might be hard to approximate to within \(2 - \varepsilon \), Approximation hardness of dominating set problems in bounded degree graphs, Approximating the online set multicover problems via randomized winnowing, Restricted parameter range promise set cover problems are easy, Inapproximability of maximal strip recovery, Precedence-constrained covering problems with multiplicity constraints, Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs, On the approximability of positive influence dominating set in social networks, On linear and semidefinite programming relaxations for hypergraph matching, Set covering approach for reconstruction of sibling relationships, Unnamed Item, Algorithmic aspects of upper edge domination, On the complexity of the minimum outer-connected dominating set problem in graphs, Inapproximability of b-Matching in k-Uniform Hypergraphs, \(\ell_1\)-sparsity approximation bounds for packing integer programs, Weighted Upper Edge Cover: Complexity and Approximability, Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs, Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs, Unnamed Item, Hardness of approximate two-level logic minimization and PAC learning with membership queries, Distributed set cover approximation: Primal-dual with optimal locality, Independent sets in bounded-degree hypergraphs, Parameterized analysis of the online priority and node-weighted Steiner tree problems, Precedence-constrained covering problems with multiplicity constraints, Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons, Degree-constrained graph orientation: maximum satisfaction and minimum violation
Cites Work
