Explanipedia

Dimension-Free Correlated Sampling for the Hypersimplex Open

K.S. Joseph, N. Appala Raju, Abhishek Shetty, Aravind Srinivasan, David Wajc · 2025

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 simplex has been a powerful building block in disparate areas …

Chasing Submodular Objectives, and Submodular Maximization via Cutting Planes Open

Niv Buchbinder, Naor, David Wajc · 2025

We introduce the \emph{submodular objectives chasing problem}, which generalizes many natural and previously-studied problems: a sequence of constrained submodular maximization problems is revealed over time, with both the objective and av…

Repairing Databases over Metric Spaces with Coincidence Constraints Open

Youri Kaminsky, Benny Kimelfeld, Ester Livshits, Felix Naumann, David Wajc · 2024

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 study the computational complexity of repairing inconsistent da…

Deterministic Online Bipartite Edge Coloring Open

Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc · 2024

We study online bipartite edge coloring, with nodes on one side of the graph revealed sequentially. The trivial greedy algorithm is $(2-o(1))$-competitive, which is optimal for graphs of low maximum degree, $Δ=O(\log n)$ [BNMN IPL'92]. Num…

New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling Open

Mark Braverman, Mahsa Derakhshan, Tristan Pollner, Amin Saberi, David Wajc · 2024

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 the graph are given upfront, while at each time $t$, an onlin…

Online Matching: A Brief Survey Open

Zhiyi Huang, Zhihao Gavin Tang, David Wajc · 2024

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 matching-based markets, many of which online in nature, has…

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs Open

Sayan Bhattacharya, Péter Kiss, Aaron Sidford, David Wajc · 2024

We study dynamic (1−є)-approximate rounding of fractional matchings—a key ingredient in numerous breakthroughs in the dynamic graph algorithms literature. Our first contribution is a surprisingly simple deterministic rounding algorithm in …

Online Edge Coloring Is (Nearly) as Easy as Offline Open

Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc · 2024

The classic theorem of Vizing (Diskret. Analiz.'64) asserts that any graph of maximum degree Δ can be edge colored (offline) using no more than Δ+1 colors (with Δ being a trivial lower bound). In the online setting, Bar-Noy, Motwani and Na…

Online Edge Coloring is (Nearly) as Easy as Offline Open

Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc · 2024

The classic theorem of Vizing (Diskret. Analiz.'64) asserts that any graph of maximum degree $Δ$ can be edge colored (offline) using no more than $Δ+1$ colors (with $Δ$ being a trivial lower bound). In the online setting, Bar-Noy, Motwani …

The Average-Value Allocation Problem Open

Kshipra Bhawalkar, Zhe Feng, Anupam Gupta, Aranyak Mehta, David Wajc , et al. · 2024

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 approximate beyond a factor of e/(e-1), and provide a 4e/(e-…

Combinatorial Stationary Prophet Inequalities Open

Neel Patel, David Wajc · 2023

Numerous recent papers have studied the tension between thickening and clearing a market in (uncertain, online) long-time horizon Markovian settings. In particular, (Aouad and Sarita{ç} EC'20, Collina et al. WINE'20, Kessel et al. EC'22) s…

Simple and Asymptotically Optimal Online Bipartite Edge Coloring Open

Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc · 2023

We provide a simple online $Δ(1+o(1))$-edge-coloring algorithm for bipartite graphs of maximum degree $Δ=ω(\log n)$ under adversarial vertex arrivals on one side of the graph. Our algorithm slightly improves the result of (Cohen, Peng and …

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs Open

Sayan Bhattacharya, P. Kiss, Aaron Sidford, David Wajc · 2023

We study dynamic $(1-ε)$-approximate rounding of fractional matchings -- a key ingredient in numerous breakthroughs in the dynamic graph algorithms literature. Our first contribution is a surprisingly simple deterministic rounding algorith…

Online Dependent Rounding Schemes for Bipartite Matchings, with Applications Open

Joseph Joseph, Naor, Aravind Srinivasan, David Wajc · 2023

We introduce the abstract problem of rounding an unknown fractional bipartite $b$-matching $\bf{x}$ revealed online (e.g., output by an online fractional algorithm), exposed node-by-node on~one~side. The objective is to maximize the \emph{…

Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time Open

Sayan Bhattacharya, P. Kiss, Thatchaphol Saranurak, David Wajc · 2022

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 approximation ratio strictly better than $2$. Specifically, we obtain a…

Improved Online Contention Resolution for Matchings and Applications to the Gig Economy Open

Tristan Pollner, Mohammad Roghani, Amin Saberi, David Wajc · 2022

Motivated by applications in the gig economy, we study approximation algorithms for a \emph{sequential pricing problem}. The input is a bipartite graph $G=(I,J,E)$ between individuals $I$ and jobs $J$. The platform has a value of $v_j$ for…

Beating the Folklore Algorithm for Dynamic Matching Open

Mohammad Roghani, Amin Saberi, David Wajc · 2022

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/time tradeoffs were obtained, improving upon the folklore a…

The Stationary Prophet Inequality Problem Open

Kristen Kessel, Amin Saberi, Ali Shameli, David Wajc · 2021

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 arrive and perish according to Poisson point processes. Buyers a…

Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities Open

Christos H. Papadimitriou, Tristan Pollner, Amin Saberi, David Wajc · 2021

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" who knows the future. An equally-natural, though significant…

Universally-optimal distributed algorithms for known topologies Open

Bernhard Haeupler, David Wajc, Goran Žužić · 2021

Many distributed optimization algorithms achieve existentially-optimal running times, meaning that there exists some pathological worst-case topology on which no algorithm can do better. Still, most networks of interest allow for exponenti…

A Randomness Threshold for Online Bipartite Matching, via Lossless Online Rounding. Open

Niv Buchbinder, Joseph Naor, David Wajc · 2021

Over three decades ago, Karp, Vazirani and Vazirani (STOC'90) introduced the online bipartite matching problem. They observed that deterministic algorithms' competitive ratio for this problem is no greater than $1/2$, and proved that rando…

Lossless Online Rounding for Online Bipartite Matching (Despite its Impossibility) Open

Niv Buchbinder, Joseph Joseph, Naor, David Wajc · 2021

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 their randomized integral counterparts. This gap is surpris…

The Greedy Algorithm is \emph{not} Optimal for On-Line Edge Coloring Open

Amin Saberi, David Wajc · 2021

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 is optimal for on-line edge coloring", shows that the comp…

Bayesian Online Matching: Approximating the Optimal Online Algorithm Open

Christos H. Papadimitriou, Tristan Pollner, Amin Saberi, David Wajc · 2021

The rich literature on online Bayesian selection problems has long focused on so-called inequalities, which compare the gain of an online algorithm to that of a prophet who knows the future. An equally-natural, though significantly less w…

Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities Open

Christos Papadimitriou, Tristan Pollner, Amin Saberi, David Wajc · 2021

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" who knows the future. An equally-natural, though significant…

Streaming Submodular Matching Meets the Primal-Dual Method Open

Roie Levin, David Wajc · 2021

We study streaming submodular maximization subject to matching/$b$-matching constraints (MSM/MSbM), and present improved upper and lower bounds for these problems. On the upper bounds front, we give primal-dual algorithms achieving the fol…

Online Edge Coloring Algorithms via the Nibble Method Open

Sayan Bhattacharya, Fabrizio Grandoni, David Wajc · 2021

Nearly thirty years ago, Bar-Noy, Motwani and Naor [IPL'92] conjectured that an online $(1+o(1))Δ$-edge-coloring algorithm exists for $n$-node graphs of maximum degree $Δ=ω(\log n)$. This conjecture remains open in general, though it was r…

Near-Optimal Schedules for Simultaneous Multicasts Open

Bernhard Haeupler, D Ellis Hershkowitz, David Wajc · 2021

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 natural generalization of the seminal work of Leighton, Magg…

The Greedy Algorithm Is not Optimal for On-Line Edge Coloring Open

Amin Saberi, David Wajc · 2021

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 is optimal for on-line edge coloring", shows that the comp…

Network Coding Gaps for Completion Times of Multiple Unicasts Open

Bernhard Haeupler, David Wajc, Goran Žužić · 2020

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 a destination specific to each packet, as fast as possible…

David Wajc YOU? Author Swipe