Correlated Online Rounding for Hypergraph Matching, and Where Adaptivity Breaks It

Many online allocation problems are hypergraph matchings. A rideshare trip serves three riders at once; a team task needs four specific workers. Each request arrives online, wants a whole bundle of $k$ resources, and must be accepted or rejected immediately. The fractional version of this problem, where we may accept a fraction of each request, is far easier than the integral one. Almost Tight Bounds for Online Hypergraph Matching shows that a deterministic water-filling rule achieves a competitive ratio of $(1-o(1))/\ln k$ fractionally, while no randomized integral algorithm beats $(2+o(1))/k$ and greedy already gets $1/k$. The remaining question is how to round, online, the fractional solution into actual accept/reject decisions, and how much of the fractional quality survives. For ordinary bipartite matching ($k=2$), Online Dependent Rounding Schemes answers this with rounding ratios of 0.652 and 0.646. For $k\ge 3$ nobody has answered it.

This proposal makes one technical observation and two claims. The observation is that bipartite online rounding works by making resource occupancies negatively correlated, which spreads risk. That is the wrong sign for hyperedges. A hyperedge is useful only if all $k$ of its resources are free at the same moment, so we want the "free" events of resources that tend to appear together to be positively correlated. The first claim is that a rounding scheme which correlates its randomness along a pairwise reduction of the hypergraph (the weighted co-occurrence graph obtained by clique expansion) beats the natural independent rounding by a constant factor when the adversary is oblivious, meaning the input sequence is fixed in advance. The second claim is that this gain, and any rounding gain over greedy, disappears against an adaptive adversary, meaning one who sees which requests were accepted before choosing the next. We want to prove that collapse, measure it, and identify the weakest adversary restriction (delayed observation or smoothed inputs) under which the gain comes back.

Core Claim

Fix the fractional solver to be water-filling, which assigns each arriving hyperedge $e$ a value $y_e\in[0,1]$, with each vertex's total load at most 1. An online rounding scheme accepts $e$ with some probability, only if all vertices of $e$ are still free. Its rounding ratio is the smallest $c_k$ such that $\Pr[e \text{ accepted}] \ge c_k\, y_e$ for every $e$.

The natural scheme scales $y_e$ down and accepts using independent coins. Its guarantee comes from a union bound over the $k$ vertices and lands near $1/(ek)$. The ceiling follows from the two bounds above: on the integral-hard instances the fractional value is at least $\mathrm{OPT}/\ln k$, while no integral algorithm exceeds $(2/k)\mathrm{OPT}$. So $c_k \le 2\ln k/k$ asymptotically.

Our target theorem has two parts. Against oblivious adversaries, a scheme exists with $c_k \ge \gamma/k$ for a constant $\gamma$ strictly above the independent scheme's constant. Against adaptive adversaries who observe realized acceptances, every online integral algorithm is within a $1+o(1)$ factor of greedy's $1/k$.

The intuition for the collapse is simple. The water-filling solver only tracks fractional loads, not which vertices were actually used. An adversary who sees a vertex become occupied can send heavy fractional mass through it. The solver pays for that mass in the fractional accounting, and the rounding can never collect it.

Research Program

The mechanism. We maintain an online clustering of the clique-expanded co-occurrence graph: vertices $u,v$ get pairwise weight equal to the accumulated fractional mass of hyperedges containing both. Vertices in a cluster share a random threshold that governs their acceptance coins, so their occupancy tends to switch together. A hyperedge lying mostly inside one cluster then finds its vertices jointly free more often than independence would give.

This uses the hypergraph-to-graph reduction in a new role. In Beyond Pairwise Clustering and Adaptive Expansion for Hypergraph Learning, the reduction exists to produce a graph that downstream algorithms consume. Here it only decides which random bits to share; the hypergraph itself stays the object we round. The analysis borrows the level-set and group-scaling ideas of Online Dependent Rounding Schemes, with the sign of the desired correlation flipped. The dependent-rounding concentration tools of Symmetric Randomized Dependent Rounding motivate the per-vertex accounting.

The hard case is a hyperedge that straddles clusters. The analysis must show that the fractional mass on such hyperedges is bounded by the clustering's cut. That reduces the problem to an online correlation-clustering-style guarantee on the expanded graph.

The impossibility side. We will construct an adaptive adversary extending the recursive blue/red gadget of Almost Tight Bounds for Online Hypergraph Matching. After each acceptance it routes new hyperedges through the just-occupied vertices. The goal is to prove the $1/k$ ceiling for any scheme whose decisions are exposed.

The precedents point the same direction. The adaptive-versus-oblivious separations in Optimal Online Discrepancy Minimization, $\Omega(\sqrt T)$ versus $O(\sqrt{\log T})$, and in Online learning over a finite action set with limited switching suggest the result is plausible. The proactive resampling of Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary is the obvious repair to try, and we expect it to fail for a specific reason. Matching decisions are irrevocable, so refreshed randomness cannot undo an occupancy the adversary already saw. A sparsifier, by contrast, can resample its outputs.

The middle ground. We will study two weakened adversaries. The first sees realized acceptances only after a lag of $\tau$ arrivals. The second must perturb its hyperedge choices with noise of smoothness $\sigma$, as in Oracle-Efficient Online Learning for Smoothed Adversaries. We aim to characterize how $c_k$ interpolates between $1/k$ and the oblivious value as $\tau$ or $\sigma$ grows. The random shift of Online Hypergraph Matching with Delays is the closest existing decorrelation device. It protects against an adversary placing hyperedges across batch boundaries, but it does not touch a fractional solver or a rounding step, and its adversary is not reactive.

Baselines

The naive reference point is greedy: accept any hyperedge whose vertices are all free. Its proved ratio is $1/k$ (Almost Tight Bounds for Online Hypergraph Matching). It needs no fractional solver, so it is the bar any LP-based method must clear, and under the adaptive adversary it is our predicted optimum. It is run on the identical arrival streams.

The strongest existing method is water-filling followed by independent scaled rounding. It uses the same fractional solver as ours, and each hyperedge is accepted with probability $\alpha y_e$ if its vertices are free, with $\alpha$ tuned per $k$ on held-out streams under the same grid we use. No reported empirical result was found on Lacuna for any online rounding of hypergraph matching. The only reported rounding ratios are for bipartite graphs, 0.652 (simple matching) and 0.646 ($b$-matching), in Online Dependent Rounding Schemes. Those serve as the $k=2$ sanity check that our implementation reproduces known behavior.

The reduction baseline applies a bipartite rounding scheme in the style of Naor–Srinivasan–Wajc to the star expansion, treating each hyperedge as an online node that must claim all its neighbors, with a repair step that rejects partial claims.

The key ablation runs our scheme with shared thresholds replaced by independent per-vertex thresholds. A second ablation clusters vertices at random rather than by co-occurrence. Together they isolate whether the gain comes from the correlation and from the reduction's choice of which vertices to correlate.

Beating the strongest baseline means a higher integral-to-fractional ratio with non-overlapping 95% confidence intervals over 50 seeds, at every $k\ge 4$, on both synthetic and real streams. All methods get identical fractional inputs and the same tuning budget.

Why not just…?

Why not just run greedy and skip the LP? Greedy's $1/k$ is close to the $2/k$ integral ceiling, so the headroom from rounding is at most a constant factor. We are honest that this is the size of the prize. The rounding route still matters for two reasons. The fractional solution certifies an instance-specific upper bound that greedy lacks. And on structured real streams, the gap between greedy and the LP value can be much larger than in the worst case. If greedy matches our scheme empirically under oblivious arrivals on DBLP and NYC streams, we will report that the oblivious-case gain is purely theoretical.

Why not just round each hyperedge independently? Independent coins ignore that a hyperedge needs all $k$ vertices free together, and the union bound loses roughly an $e$ factor. The independent-threshold ablation tests directly whether shared randomness recovers this. If it does not, the correlation idea is wrong and the paper reduces to the impossibility result.

Why not just reduce to a bipartite graph and reuse existing online dependent rounding? That scheme enforces negative correlation of occupancy across offline vertices, which is the right sign for $k=2$ and the wrong sign for joint availability. The reduction baseline measures exactly this. We predict it underperforms independent rounding as $k$ grows. If it does not, our sign argument is mistaken.

Why not just keep the oblivious adversary, as the existing hypergraph work does? In ridesharing, arrivals do react to what was served: riders rebook and platforms reposition. Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification explicitly leaves the adaptive case open for related hypergraph problems. Showing that rounding gains vanish under adaptivity is itself a useful negative result. It tells practitioners when an LP-based pipeline is worth building.

Proposed Experiments

Synthetic streams. We generate $k$-uniform streams for $k\in\{2,\dots,10\}$ under three arrival models: uniform random, the blue/red gadget family, and power-law co-occurrence.

Real hypergraphs. The co-authorship hypergraphs DBLP and Cora-CA and the co-sponsorship hypergraphs Senate and House come from the Adaptive Expansion for Hypergraph Learning benchmark suite. They are replayed as packing streams in publication or session order with unit vertex capacity. We also build shareability hypergraphs from the NYC Taxi December 30 trace used in Online Ridesharing with Meeting Points. That paper's 33.1% served-request improvement over GreedyDP is for a different routing problem and is context only, not a baseline.

Metrics. We report the integral value divided by the water-filling value (empirical $c_k$) and the integral value divided by the offline LP optimum.

Adversary conditions. Each method faces an oblivious stream, a fixed adaptive adversary that targets just-occupied vertices, a search-based adaptive adversary that runs a depth-3 lookahead over candidate next hyperedges using the realized state, and lagged and smoothed variants across a sweep of $\tau$ and $\sigma$.

Decisive checks. Three outcomes settle the proposal. First, on oblivious streams our scheme should beat the independent-threshold ablation at every $k\ge4$, with a margin that does not shrink with $k$. Second, under the search-based adaptive adversary every method should fall to within a few percent of greedy, confirming the collapse. Third, the lag sweep should show the empirical $c_k$ returning monotonically toward its oblivious value as $\tau$ grows. If the first check fails, the correlation mechanism is refuted. If the second fails, our impossibility conjecture is wrong and the adaptive repair becomes the main contribution.