Simpler and Stronger Approaches for Non-Uniform Hypergraph Matching and the Füredi, Kahn, and Seymour Conjecture
METADATA ONLY
Loading...
Author / Producer
Date
2021
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
A well-known conjecture of Füredi, Kahn, and Seymour (1993) on non-uniform hypergraph matching states that for any hypergraph with edge weights w, there exists a matching M such that the inequality Σe∊M g(e)w(e) ≥ OPTLP holds with g(e) = |e| – 1 +1/|e|, where OPTLP denotes the optimal value of the canonical LP relaxation. While the conjecture remains open, the strongest result towards it was recently obtained by Brubach, Sankararaman, Srinivasan, and Xu (2020)—building on and strengthening prior work by Bansal, Gupta, Li, Mestre, Nagarajan, and Rudra (2012)—showing that the aforementioned inequality holds with g(e) = |e| + O(|e| exp(–|e|)). Actually, their method works in a more general sampling setting, where, given a point x of the canonical LP relaxation, the task is to efficiently sample a matching M containing each edge e with probability at leastx(e)/g(e).
We present simpler and easy-to-analyze procedures leading to improved results. More precisely, for any solution x to the canonical LP, we introduce a simple algorithm based on exponential clocks for Brubach et al.'s sampling setting achieving g(e) = |e| – (|e|-1)x(e). Apart from the slight improvement in g, our technique may open up new ways to attack the original conjecture. Moreover, we provide a short and arguably elegant analysis showing that a natural greedy approach for the original setting of the conjecture shows the inequality for the same g(e) = |e| – (|e| – 1)x(e) even for the more general hypergraph b-matching problem.
Read More: https://epubs.siam.org/doi/10.1137/1.9781611976496.22
Permanent link
Publication status
published
External links
Book title
Proceedings Symposium on Simplicity in Algorithms (SOSA)
Journal / series
Volume
Pages / Article No.
196 - 203
Publisher
SIAM
Event
4th Symposium on Simplicity in Algorithms (SOSA 2021)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
09487 - Zenklusen, Rico / Zenklusen, Rico
Notes
Funding
817750 - Fundamental Problems at the Interface of Combinatorial Optimization with Integer Programming and Online Optimization (EC)
184622 - Toward Stronger Approximation Algorithms for Fundamental Network Design and Optimization Problems (SNF)
184622 - Toward Stronger Approximation Algorithms for Fundamental Network Design and Optimization Problems (SNF)