A black-box batching extension preserves the competitive ratio of any online resource allocation algorithm under exogenous replenishment, asymptotically when starting inventory is large, plus an impossibility result for large stochastic replenishments.
Almost Tight Bounds for Online Hypergraph Matching
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
In the online hypergraph matching problem, hyperedges of size $k$ over a common ground set arrive online in adversarial order. The goal is to obtain a maximum matching (disjoint set of hyperedges). A na\"ive greedy algorithm for this problem achieves a competitive ratio of $\frac{1}{k}$. We show that no (randomized) online algorithm has competitive ratio better than $\frac{2+o(1)}{k}$. If edges are allowed to be assigned fractionally, we give a deterministic online algorithm with competitive ratio $\frac{1-o(1)}{\ln(k)}$ and show that no online algorithm can have competitive ratio strictly better than $\frac{1+o(1)}{\ln(k)}$. Lastly, we give a $\frac{1-o(1)}{\ln(k)}$ competitive algorithm for the fractional edge-weighted version of the problem under a free disposal assumption.
citation-role summary
other 1
citation-polarity summary
fields
cs.DS 1years
2025 1verdicts
CONDITIONAL 1roles
other 1polarities
unclear 1representative citing papers
citing papers explorer
-
A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
A black-box batching extension preserves the competitive ratio of any online resource allocation algorithm under exogenous replenishment, asymptotically when starting inventory is large, plus an impossibility result for large stochastic replenishments.