10 citations · 23 across the 21 of their papers we have counts for
35 papers
Online Submodular Welfare Maximization: Computation is not the Bottleneck
Rajan Udwani, David Wajc
We revisit the online submodular welfare maximization problem (OSW), a vast generalization of numerous well-studied online allocation problems, including online bipartite matching,…
Asymptotically Tight Fractional Online Matching Under Edge Arrivals
David Wajc
In this brief note, we close the asymptotic gap between known upper and lower bounds for fractional online matching under edge arrivals. We prove that the optimal competitive ratio…
Chasing Submodular Objectives, and Submodular Maximization via Cutting Planes
Niv Buchbinder, Joseph, Naor +1
We introduce the \emph{submodular objectives chasing problem}, which generalizes many natural and previously-studied problems: a sequence of constrained submodular maximization pro…
Dimension-Free Correlated Sampling for the Hypersimplex
Joseph, Naor, Nitya Raju +4
Sampling from multiple distributions so as to maximize overlap has been studied by statisticians since the 1950s. Since the 2000s, such correlated sampling from the probability sim…
Online Edge Coloring: Sharp Thresholds
Joakim Blikstad, Ola Svensson, Radu Vintan +1
Vizing's theorem guarantees that every graph with maximum degree admits an edge coloring using colors. In online settings - where edges arrive one at a time and must be…
Repairing Databases over Metric Spaces with Coincidence Constraints
Youri Kaminsky, Benny Kimelfeld, Ester Livshits +2
Datasets often contain values that naturally reside in a metric space: numbers, strings, geographical locations, machine-learned embeddings in a Euclidean space, and so on. We stud…