227 citations
- Hebrew University of JerusalemIL26 papers
- Microsoft (United States)US18 papers
- Tel Aviv UniversityIL18 papers
- Technion – Israel Institute of TechnologyIL14 papers
- Google (United States)US7 papers
- Microsoft Research (United Kingdom)GB5 papers
- Bar-Ilan UniversityIL4 papers
- Stanford UniversityUS4 papers
- Centre National de la Recherche ScientifiqueFR3 papers
- Cornell UniversityUS3 papers
- University of Illinois Urbana-ChampaignUS3 papers
- Weizmann Institute of ScienceIL3 papers
4 papers · 1 filter
Approximating the Statistics of various Properties in Randomly Weighted Graphs
Yuval Emek, Amos Korman, Yuval Shavitt
Consider the setting of \emph{randomly weighted graphs}, namely, graphs whose edge weights are chosen independently according to probability distributions with finite support over…
Auctions with Online Supply
Moshe Babaioff, Liad Blumrosen, Aaron L. Roth
We study the problem of selling identical goods to n unit-demand bidders in a setting in which the total supply of goods is unknown to the mechanism. Items arrive dynamically, and…
Sums and products along sparse graphs
Noga Alon, Omer Angel, Itai Benjamini +1
In their seminal paper from 1983, Erdős and Szemerédi showed that any distinct integers induce either distinct sums of pairs or that many distinct products, and conje…
On the Additive Constant of the k-server Work Function Algorithm
Yuval Emek, Pierre Fraigniaud, Amos Korman +1
We consider the Work Function Algorithm for the k-server problem. We show that if the Work Function Algorithm is c-competitive, then it is also strictly (2c)-competitive. As a cons…