On the complexity of approximating \(k\)-set packing
From MaRDI portal
Publication:2506163
DOI10.1007/s00037-006-0205-6zbMath1103.90105OpenAlexW1966923282WikidataQ57310535 ScholiaQ57310535MaRDI QIDQ2506163
Elad Hazan, Oded Schwartz, Shmuel Safra
Publication date: 28 September 2006
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-006-0205-6
Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (45)
Shrinking maxima, decreasing costs: new online packing and covering problems ⋮ Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs ⋮ Generalized Hypergraph Matching via Iterated Packing and Local Ratio ⋮ From the quantum approximate optimization algorithm to a quantum alternating operator ansatz ⋮ Online Admission Control and Embedding of Service Chains ⋮ Submodular Stochastic Probing on Matroids ⋮ Hypergraph representation via axis-aligned point-subspace cover ⋮ A computational approach to unbiased districting ⋮ The limits of local search for weighted \(k\)-set packing ⋮ The quality of equilibria for set packing and throughput scheduling games ⋮ Competitive buffer management with packet dependencies ⋮ Maximum coverage problem with group budget constraints ⋮ Inapproximability of $H$-Transversal/Packing ⋮ On the parameterized complexity of compact set packing ⋮ Technical Note—Online Hypergraph Matching with Delays ⋮ Coupled and \(k\)-sided placements: generalizing generalized assignment ⋮ Submodular Maximization Through the Lens of Linear Programming ⋮ Exponential inapproximability of selecting a maximum volume sub-matrix ⋮ \(k\)-optimal: a novel approximate inference algorithm for ProbLog ⋮ A 6/5-approximation algorithm for the maximum 3-cover problem ⋮ Approximability of sparse integer programs ⋮ Unnamed Item ⋮ A Lower Bound of the cd-Chromatic Number and Its Complexity ⋮ Scheduling split intervals with non-uniform demands ⋮ Distributed approximation of \(k\)-service assignment ⋮ Bin packing with fragmentable items: presentation and approximations ⋮ Distributed backup placement in networks ⋮ Iterative Packing for Demand and Hypergraph Matching ⋮ Greedy matching: guarantees and limitations ⋮ Combinatorial auctions without money ⋮ When LP is the cure for your matching woes: improved bounds for stochastic matchings ⋮ Inapproximability of maximal strip recovery ⋮ On linear and semidefinite programming relaxations for hypergraph matching ⋮ A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem ⋮ Combinatorial auctions with verification are tractable ⋮ Flexible allocation on related machines with assignment restrictions ⋮ An Approximation Result for Matchings in Partitioned Hypergraphs ⋮ Constrained submodular maximization via greedy local search ⋮ Overflow management with self-eliminations ⋮ Inapproximability of b-Matching in k-Uniform Hypergraphs ⋮ \(\ell_1\)-sparsity approximation bounds for packing integer programs ⋮ Overflow management with self-eliminations ⋮ On approximating four covering and packing problems ⋮ Online Submodular Maximization Problem with Vector Packing Constraint. ⋮ Distributed algorithms for matching in hypergraphs
This page was built for publication: On the complexity of approximating \(k\)-set packing
