Inapproximability of b-Matching in k-Uniform Hypergraphs
DOI10.1007/978-3-642-19094-0_8zbMath1317.68068OpenAlexW164187068MaRDI QIDQ3078381
Antje Fretwurst, Anand Srivastav, Mourad El Ouali
Publication date: 20 February 2011
Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-19094-0_8
colorabilityapproximation algorithmsNP-hardnessprobabilistic methodshardness of approximationgap problem
Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the fractional matching polytope of a hypergraph
- Efficient bounds for the stable set, vertex cover and set packing problems
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- On the ratio of optimal integral and fractional covers
- On the complexity of approximating \(k\)-set packing
- Proof verification and the hardness of approximation problems
- On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
- Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems
- Probabilistic checking of proofs
- Randomized greedy matching. II
- Asymptotic packing via a branching process
- Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
- Improved Approximation Guarantees for Packing and Covering Integer Programs
- Non-approximability results for optimization problems on bounded degree instances
- Some optimal inapproximability results
- Mathematical Foundations of Computer Science 2005
