7 papers
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…
The Average-Value Allocation Problem
Kshipra Bhawalkar, Zhe Feng, Anupam Gupta +3
We initiate the study of centralized algorithms for welfare-maximizing allocation of goods to buyers subject to average-value constraints. We show that this problem is NP-hard to a…
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 b…
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…