421 citations
Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.
- University College LondonGB63 papers
- Systemic Risk CentreGB48 papers
- University of OxfordGB20 papers
- University of WarwickGB18 papers
- King's College LondonGB16 papers
- London Mathematical LaboratoryGB12 papers
- University of Illinois Urbana-ChampaignUS12 papers
- Centre National de la Recherche ScientifiqueFR11 papers
- Queen Mary University of LondonGB11 papers
- The Open UniversityGB11 papers
- City, University of LondonGB10 papers
- ETH ZurichCH10 papers
15 papers · 1 filter
Single-Sample Prophet Inequalities via Greedy-Ordered Selection
Constantine Caramanis, Paul Dütting, Matthew Faw +6
We study single-sample prophet inequalities (SSPIs), i.e., prophet inequalities where only a single sample from each prior distribution is available. Besides a direct, and optimal,…
The Complexity of Contracts
Paul Duetting, Tim Roughgarden, Inbal Talgam-Cohen
We initiate the study of computing (near-)optimal contracts in succinctly representable principal-agent settings. Here optimality means maximizing the principal's expected payoff o…
On the extension complexity of scheduling
Hans Raj Tiwary, Victor Verdugo, Andreas Wiese
Linear programming is a powerful method in combinatorial optimization with many applications in theory and practice. For solving a linear program quickly it is desirable to have a…
Prophet Inequalities for I.I.D. Random Variables from an Unknown Distribution
José R. Correa, Paul Dütting, Felix Fischer +1
A central object in optimal stopping theory is the single-choice prophet inequality for independent, identically distributed random variables: Given a sequence of random variables…
Skyline Computation with Noisy Comparisons
Benoît Groz, Frederik Mallmann-Trenn, Claire Mathieu +1
Given a set of points in a -dimensional space, we seek to compute the skyline, i.e., those points that are not strictly dominated by any other point, using few comparisons b…
Communication complexity of approximate maximum matching in the message-passing model
Zengfeng Huang, Bozidar Radunovic, Milan Vojnovic +1
We consider the communication complexity of finding an approximate maximum matching in a graph in a multi-party message-passing communication model. The maximum matching problem is…
Submodular Maximization using Test Scores
Shreyas Sekar, Milan Vojnovic, Se-Young Yun
We study the canonical problem of maximizing a stochastic submodular function subject to a cardinality constraint, where the goal is to select a subset from a ground set of items w…
Constant Factor Approximation for ATSP with Two Edge Weights
Ola Svensson, Jakub Tarnawski, László A. Végh
We give a constant factor approximation algorithm for the Asymmetric Traveling Salesman Problem on shortest path metrics of directed graphs with two different edge weights. For the…
A Rational Convex Program for Linear Arrow-Debreu Markets
Nikhil R. Devanur, Jugal Garg, László A. Végh
We give a new, flow-type convex program describing equilibrium solutions to linear Arrow-Debreu markets. Whereas convex formulations were previously known [Nenakov, Primak 83; Jain…
A strongly polynomial algorithm for generalized flow maximization
László A. Végh
A strongly polynomial algorithm is given for the generalized flow maximization problem. It uses a new variant of the scaling technique, called continuous scaling. The main measure…
Fixed-parameter algorithms for minimum cost edge-connectivity augmentation
Dániel Marx, László A. Végh
We consider connectivity-augmentation problems in a setting where each potential new edge has a nonnegative cost associated with it, and the task is to achieve a certain connectivi…
The Cutting Plane Method is Polynomial for Perfect Matchings
Karthekeyan Chandrasekaran, Laszlo A. Vegh, Santosh Vempala
The cutting plane approach to optimal matchings has been discussed by several authors over the past decades (e.g., Padberg and Rao '82, Grotschel and Holland '85, Lovasz and Plumme…
Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives
Laszlo A. Vegh
A well-studied nonlinear extension of the minimum-cost flow problem is to minimize the objective over feasible flows , where on every arc of…
Testing Closeness of Discrete Distributions
Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld +2
Given samples from two distributions over an -element set, we wish to test whether these distributions are statistically close. We present an algorithm which uses sublinear in $…
Chains-into-Bins Processes
Tugkan Batu, Petra Berenbrink, Colin Cooper
The study of {\em balls-into-bins processes} or {\em occupancy problems} has a long history. These processes can be used to translate realistic problems into mathematical ones in a…