309 citations · 1.1k across the 60 of their papers we have counts for
19 papers · 1 filter
Breaking the VLB Barrier for Oblivious Reconfigurable Networks
Tegan Wilson, Daniel Amir, Nitika Saran +3
In a landmark 1981 paper, Valiant and Brebner gave birth to the study of oblivious routing and, simultaneously, introduced its most powerful and ubiquitous method: Valiant load bal…
Individual Fairness in Prophet Inequalities
Makis Arsenis, Robert Kleinberg
Prophet inequalities are performance guarantees for online algorithms (a.k.a. stopping rules) solving the following "hiring problem": a decision maker sequentially inspects candida…
Optimal Oblivious Reconfigurable Networks
Daniel Amir, Tegan Wilson, Vishal Shrivastav +3
Oblivious routing has a long history in both the theory and practice of networking. In this work we initiate the formal study of oblivious routing in the context of reconfigurable…
Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem
Hyung-Chan An, Robert Kleinberg, David B. Shmoys
We present the first nontrivial approximation algorithm for the bottleneck asymmetric traveling salesman problem. Given an asymmetric metric cost between n vertices, the problem is…
Constrained-Order Prophet Inequalities
Makis Arsenis, Odysseas Drosis, Robert Kleinberg
Free order prophet inequalities bound the ratio between the expected value obtained by two parties each selecting a value from a set of independent random variables: a "prophet" wh…
Beating 1-1/e for Ordered Prophets
Melika Abolhasani, Soheil Ehsani, Hosein Esfandiari +3
Hill and Kertz studied the prophet inequality on iid distributions [The Annals of Probability 1982]. They proved a theoretical bound of on the approximation factor…
Simultaneous Nearest Neighbor Search
Piotr Indyk, Robert Kleinberg, Sepideh Mahabadi +1
Motivated by applications in computer vision and databases, we introduce and study the Simultaneous Nearest Neighbor Search (SNN) problem. Given a set of data points, the goal of S…
Inferential Privacy Guarantees for Differentially Private Mechanisms
Arpita Ghosh, Robert Kleinberg
The correlations and network structure amongst individuals in datasets today---whether explicitly articulated, or deduced from biological or behavioral connections---pose new issue…
Secretary Problems with Non-Uniform Arrival Order
Thomas Kesselheim, Robert Kleinberg, Rad Niazadeh
For many online problems, it is known that the uniform arrival order enables the design of algorithms with much better performance guarantees than under worst-case. The quintessent…
Bandits and Experts in Metric Spaces
Robert Kleinberg, Aleksandrs Slivkins, Eli Upfal
In a multi-armed bandit problem, an online algorithm chooses from a set of strategies in a sequence of trials so as to maximize the total payoff of the chosen strategies. While the…
A Unified Approach to Online Allocation Algorithms via Randomized Dual Fitting
Rad Niazadeh, Robert D. Kleinberg
We present a unified framework for designing and analyzing algorithms for online budgeted allocation problems (including online matching) and their generalization, the Online Gener…
Trace Complexity of Network Inference
Bruno Abrahao, Flavio Chierichetti, Robert Kleinberg +1
The network inference problem consists of reconstructing the edge set of a network given traces representing the chronology of infection times as epidemics spread through the netwo…
Polymatroid Prophet Inequalities
Paul Duetting, Robert Kleinberg
Consider a gambler and a prophet who observe a sequence of independent, non-negative numbers. The gambler sees the numbers one-by-one whereas the prophet sees the entire sequence a…
Prophet Inequalities with Limited Information
Pablo D. Azar, Robert Kleinberg, S. Matthew Weinberg
In the classical prophet inequality, a gambler observes a sequence of stochastic rewards and must decide, for each reward , whether to keep it and stop the game…
Bandits with Knapsacks
Ashwinkumar Badanidiyuru, Robert Kleinberg, Aleksandrs Slivkins
Multi-armed bandit problems are the predominant theoretical model of exploration-exploitation tradeoffs in learning, and they have countless applications ranging from medical trial…
Matroid Prophet Inequalities
Robert Kleinberg, S. Matthew Weinberg
Consider a gambler who observes a sequence of independent, non-negative random numbers and is allowed to stop the sequence at any time, claiming a reward equal to the most recent o…
Improving Christofides' Algorithm for the s-t Path TSP
Hyung-Chan An, Robert Kleinberg, David B. Shmoys
We present a deterministic (1+sqrt(5))/2-approximation algorithm for the s-t path TSP for an arbitrary metric. Given a symmetric metric cost on n vertices including two prespecifie…
Sharp Dichotomies for Regret Minimization in Metric Spaces
Robert Kleinberg, Aleksandrs Slivkins
The Lipschitz multi-armed bandit (MAB) problem generalizes the classical multi-armed bandit problem by assuming one is given side information consisting of a priori upper bounds on…
Multi-Armed Bandits in Metric Spaces
Robert Kleinberg, Aleksandrs Slivkins, Eli Upfal
In a multi-armed bandit problem, an online algorithm chooses from a set of strategies in a sequence of trials so as to maximize the total payoff of the chosen strategies. While the…