Generalized hypergraph matching via iterated packing and local ratio

DOI10.1007/978-3-319-18263-6_18MaRDI QIDQ3453296zbMATH OpenOpenAlexFDO

Authors

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

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)

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.

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

Cites work

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

Cited in

(10)

• Constant factor approximation for the weighted partial degree bounded edge packing problem
• 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
• Efficient implementation of Carathéodory's theorem for the single machine scheduling polytope
• How to sell hyperedges: the hypermatching assignment problem
• Iterative packing for demand and hypergraph matching
• 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)