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