Generalized hypergraph matching via iterated packing and local ratio

DOI10.1007/978-3-319-18263-6_18zbMATH Open1457.68310arXiv1604.00322OpenAlexW3098952651MaRDI QIDQ3453296FDOQ3453296

Authors:

Publication date: 20 November 2015

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

Abstract: In $k$-hypergraph matching, we are given a collection of sets of size at most $k$, each with an associated weight, and we seek a maximum-weight subcollection whose sets are pairwise disjoint. More generally, in $k$-hypergraph $b$-matching, instead of disjointness we require that every element appears in at most $b$ sets of the subcollection. Our main result is a linear-programming based $(k-1+frac1k)$-approximation algorithm for $k$-hypergraph $b$-matching. This settles the integrality gap when $k$ is one more than a prime power, since it matches a previously-known lower bound. When the hypergraph is bipartite, we are able to improve the approximation ratio to $k-1$, which is also best possible relative to the natural LP. These results are obtained using a more careful application of the emph{iterated packing} method. Using the bipartite algorithmic integrality gap upper bound, we show that for the family of combinatorial auctions in which anyone can win at most $t$ items, there is a truthful-in-expectation polynomial-time auction that $t$-approximately maximizes social welfare. We also show that our results directly imply new approximations for a generalization of the recently introduced bounded-color matching problem. We also consider the generalization of $b$-matching to emph{demand matching}, where edges have nonuniform demand values. The best known approximation algorithm for this problem has ratio $2k$ on $k$-hypergraphs. We give a new algorithm, based on local ratio, that obtains the same approximation ratio in a much simpler way.

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

Recommendations

• Iterative packing for demand and hypergraph matching
• How to sell hyperedges: the hypermatching assignment problem
• Inapproximability of \(b\)-matching in \(k\)-uniform hypergraphs
• The \(b\)-matching problem in hypergraphs: hardness and approximability
• An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• Approximate multi-matroid intersection via iterative refinement
• Constant factor approximation for the weighted partial degree bounded edge packing problem
• Emergence and dynamics of short food supply chains
• 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
• Stochastic packing integer programs with few queries
• Inapproximability of \(b\)-matching in \(k\)-uniform hypergraphs
• Integrality gaps for colorful matchings

This page was built for publication: Generalized hypergraph matching via iterated packing and local ratio

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3453296)