Generalized Hypergraph Matching via Iterated Packing and Local Ratio

DOI10.1007/978-3-319-18263-6_18zbMath1457.68310arXiv1604.00322OpenAlexW3098952651MaRDI QIDQ3453296

No author found.

Publication date: 20 November 2015

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1604.00322

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Auctions, bargaining, bidding and selling, and other market models (91B26) Approximation algorithms (68W25)

Related Items

Constant factor approximation for the weighted partial degree bounded edge packing problem ⋮ Efficient implementation of Carathéodory's theorem for the single machine scheduling polytope ⋮ Integrality gaps for colorful matchings ⋮ Stochastic packing integer programs with few queries ⋮ Constant Factor Approximation for the Weighted Partial Degree Bounded Edge Packing Problem ⋮ Emergence and dynamics of short food supply chains ⋮ Approximate multi-matroid intersection via iterative refinement

Cites Work

• On the fractional matching polytope of a hypergraph
• On linear and semidefinite programming relaxations for hypergraph matching
• On a possible extension of Hall's theorem to bipartite hypergraphs
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Maximum degree and fractional matchings in uniform hypergraphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On the complexity of approximating \(k\)-set packing
• On Local Search for Weighted k-Set Packing
• Approximation Algorithms for Bounded Color Matchings via Convex Decompositions
• Iterative Packing for Demand and Hypergraph Matching
• Improved Approximations for k-Exchange Systems
• 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
• Edge Coloring and Decompositions of Weighted Graphs
• On k-Column Sparse Packing Programs
• Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality
• Randomized metarounding
• The Demand-Matching Problem
• Algorithmic Game Theory
• Scheduling Split Intervals
• On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique
• A Short Proof of the Factor Theorem for Finite Graphs