10 citations · 23 across the 21 of their papers we have counts for
32 papers · 1 filter
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…
Deterministic Online Bipartite Edge Coloring
Joakim Blikstad, Ola Svensson, Radu Vintan +1
We study online bipartite edge coloring, with nodes on one side of the graph revealed sequentially. The trivial greedy algorithm is -competitive, which is optimal for gra…
New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling
Mark Braverman, Mahsa Derakhshan, Tristan Pollner +2
We study the polynomial-time approximability of the optimal online stochastic bipartite matching algorithm, initiated by Papadimitriou et al. (EC'21). Here, nodes on one side of th…
Online Matching: A Brief Survey
Zhiyi Huang, Zhihao Gavin Tang, David Wajc
Matching, capturing allocation of items to unit-demand buyers, or tasks to workers, or pairs of collaborators, is a central problem in economics. Indeed, the growing prevalence of…
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 is (Nearly) as Easy as Offline
Joakim Blikstad, Ola Svensson, Radu Vintan +1
The classic theorem of Vizing (Diskret. Analiz.'64) asserts that any graph of maximum degree can be edge colored (offline) using no more than colors (with being a tri…
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…
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak +1
We present dynamic algorithms with polylogarithmic update time for estimating the size of the maximum matching of a graph undergoing edge insertions and deletions with approximatio…
Improved Online Contention Resolution for Matchings and Applications to the Gig Economy
Tristan Pollner, Mohammad Roghani, Amin Saberi +1
Motivated by applications in the gig economy, we study approximation algorithms for a \emph{sequential pricing problem}. The input is a bipartite graph between individu…
The Stationary Prophet Inequality Problem
Kristen Kessel, Amin Saberi, Ali Shameli +1
We study a continuous and infinite time horizon counterpart to the classic prophet inequality, which we term the stationary prophet inequality problem. Here, copies of a good arriv…
Beating the Folklore Algorithm for Dynamic Matching
Mohammad Roghani, Amin Saberi, David Wajc
The maximum matching problem in dynamic graphs subject to edge updates (insertions and deletions) has received much attention over the last few years; a multitude of approximation/…
Lossless Online Rounding for Online Bipartite Matching (Despite its Impossibility)
Niv Buchbinder, Joseph, Naor +1
For numerous online bipartite matching problems, such as edge-weighted matching and matching under two-sided vertex arrivals, the state-of-the-art fractional algorithms outperform…
The Greedy Algorithm is \emph{not} Optimal for On-Line Edge Coloring
Amin Saberi, David Wajc
Nearly three decades ago, Bar-Noy, Motwani and Naor showed that no online edge-coloring algorithm can edge color a graph optimally. Indeed, their work, titled "the greedy algorithm…
Universally-Optimal Distributed Algorithms for Known Topologies
Bernhard Haeupler, David Wajc, Goran Zuzic
Many distributed optimization algorithms achieve existentially-optimal running times, meaning that there exists some pathological worst-case topology on which no algorithm can do b…
Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities
Christos Papadimitriou, Tristan Pollner, Amin Saberi +1
The rich literature on online Bayesian selection problems has long focused on so-called prophet inequalities, which compare the gain of an online algorithm to that of a "prophet" w…
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)…
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…
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…