10 citations · 23 across the 21 of their papers we have counts for
6 papers · 1 filter
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…
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…