10 citations · 23 across the 21 of their papers we have counts for
5 papers · 1 filter
Rounding Dynamic Matchings Against an Adaptive Adversary
David Wajc
We present a new dynamic matching sparsification scheme. From this scheme we derive a framework for dynamically rounding fractional matchings against \emph{adaptive adversaries}. P…
Network Coding Gaps for Completion Times of Multiple Unicasts
Bernhard Haeupler, David Wajc, Goran Zuzic
We study network coding gaps for the problem of makespan minimization of multiple unicasts. In this problem distinct packets at different nodes in a network need to be delivered to…
Stochastic Online Metric Matching
Anupam Gupta, Guru Guruganesh, Binghui Peng +1
We study the minimum-cost metric perfect matching problem under online i.i.d arrivals. We are given a fixed metric with a server at each of the points, and then requests arrive onl…
Tight Bounds for Online Edge Coloring
Ilan Reuven Cohen, Binghui Peng, David Wajc
Vizing's celebrated theorem asserts that any graph of maximum degree admits an edge coloring using at most colors. In contrast, Bar-Noy, Naor and Motwani showed over a qu…
Online Matching with General Arrivals
Buddhima Gamlath, Michael Kapralov, Andreas Maggiori +2
The online matching problem was introduced by Karp, Vazirani and Vazirani nearly three decades ago. In that seminal work, they studied this problem in bipartite graphs with vertice…