10 citations · 23 across the 21 of their papers we have counts for
Showing 2020Show all
3 papers · 1 filter
cs.DS2020
Online Edge Coloring Algorithms via the Nibble Method
Sayan Bhattacharya, Fabrizio Grandoni, David Wajc
Nearly thirty years ago, Bar-Noy, Motwani and Naor [IPL'92] conjectured that an online -edge-coloring algorithm exists for -node graphs of maximum degree $Δ=ω(\log n)…
cs.DS2020
Streaming Submodular Matching Meets the Primal-Dual Method
Roie Levin, David Wajc
We study streaming submodular maximization subject to matching/-matching constraints (MSM/MSbM), and present improved upper and lower bounds for these problems. On the upper bou…
cs.DS2020★ 3 cited
Near-Optimal Schedules for Simultaneous Multicasts
Bernhard Haeupler, D Ellis Hershkowitz, David Wajc
We study the store-and-forward packet routing problem for simultaneous multicasts, in which multiple packets have to be forwarded along given trees as fast as possible. This is a n…