10 citations · 23 across the 21 of their papers we have counts for
4 papers · 1 filter
Combinatorial Stationary Prophet Inequalities
Neel Patel, David Wajc
Numerous recent papers have studied the tension between thickening and clearing a market in (uncertain, online) long-time horizon Markovian settings. In particular, (Aouad and Sari…
Simple and Asymptotically Optimal Online Bipartite Edge Coloring
Joakim Blikstad, Ola Svensson, Radu Vintan +1
We provide a simple online -edge-coloring algorithm for bipartite graphs of maximum degree under adversarial vertex arrivals on one side of the graph. Our…
Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
Sayan Bhattacharya, Peter Kiss, Aaron Sidford +1
We study dynamic -approximate rounding of fractional matchings -- a key ingredient in numerous breakthroughs in the dynamic graph algorithms literature. Our first contributi…
Online Dependent Rounding Schemes for Bipartite Matchings, with Applications
Joseph, Naor, Aravind Srinivasan +1
We introduce the abstract problem of rounding an unknown fractional bipartite -matching revealed online (e.g., output by an online fractional algorithm), exposed node-b…