Pages that link to "Item:Q5176001"
From MaRDI portal
The following pages link to Non-approximability results for optimization problems on bounded degree instances (Q5176001):
Displaying 50 items.
- Degree-constrained graph orientation: maximum satisfaction and minimum violation (Q260260) (← links)
- Deterministic versus randomized adaptive test cover (Q329717) (← links)
- Complexity of majority monopoly and signed domination problems (Q414422) (← links)
- Approximating vertex cover in dense hypergraphs (Q450531) (← links)
- Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs (Q491613) (← links)
- Inapproximability of maximal strip recovery (Q551208) (← links)
- Approximability of sparse integer programs (Q634673) (← links)
- On linear and semidefinite programming relaxations for hypergraph matching (Q715088) (← links)
- Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs (Q839632) (← links)
- On the configuration LP for maximum budgeted allocation (Q896296) (← links)
- Approximation hardness of dominating set problems in bounded degree graphs (Q958303) (← links)
- Independent sets in bounded-degree hypergraphs (Q1026137) (← links)
- Hardness of approximation for non-overlapping local alignments. (Q1427808) (← links)
- Approximating weighted neighborhood independent sets (Q1679903) (← links)
- Donation center location problem (Q1949758) (← links)
- On the approximability of positive influence dominating set in social networks (Q2015789) (← links)
- Algorithmic aspects of upper edge domination (Q2034795) (← links)
- Precedence-constrained covering problems with multiplicity constraints (Q2085754) (← links)
- On regularity of Max-CSPs and Min-CSPs (Q2122790) (← links)
- Learning in auctions: regret is hard, envy is easy (Q2155904) (← links)
- Optimal item pricing in online combinatorial auctions (Q2164686) (← links)
- Restricted parameter range promise set cover problems are easy (Q2258109) (← links)
- Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs (Q2266936) (← links)
- Parameterized analysis of the online priority and node-weighted Steiner tree problems (Q2322716) (← links)
- Complexity of approximating bounded variants of optimization problems (Q2368970) (← links)
- Primal-dual algorithms for precedence constrained covering problems (Q2408089) (← links)
- Randomized scheduling algorithm for queueing networks (Q2428047) (← links)
- Scheduling to minimize gaps and power consumption (Q2434309) (← links)
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \) (Q2475406) (← links)
- Approximating the online set multicover problems via randomized winnowing (Q2481951) (← links)
- Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons (Q2575833) (← links)
- Inapproximability of b-Matching in k-Uniform Hypergraphs (Q3078381) (← links)
- Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs (Q3088105) (← links)
- Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs (Q3088179) (← links)
- Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs (Q3304731) (← links)
- Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces (Q3451756) (← links)
- Primal-Dual Algorithms for Precedence Constrained Covering Problems (Q3453300) (← links)
- Partial Resampling to Approximate Covering Integer Programs (Q4575724) (← links)
- Tandem Duplications, Segmental Duplications and Deletions, and Their Applications (Q5042229) (← links)
- Distributed set cover approximation: Primal-dual with optimal locality (Q5090914) (← links)
- (Q5092472) (← links)
- Technical Note—Online Hypergraph Matching with Delays (Q5106363) (← links)
- Clustering in Hypergraphs to Minimize Average Edge Service Time (Q5111753) (← links)
- (Q5121893) (← links)
- Weighted Upper Edge Cover: Complexity and Approximability (Q5216282) (← links)
- Set covering approach for reconstruction of sibling relationships (Q5758164) (← links)
- \(\ell_1\)-sparsity approximation bounds for packing integer programs (Q5918913) (← links)
- Hardness of approximate two-level logic minimization and PAC learning with membership queries (Q5920702) (← links)
- On the complexity of the minimum outer-connected dominating set problem in graphs (Q5963605) (← links)
- Precedence-constrained covering problems with multiplicity constraints (Q6039535) (← links)
