research
∙
01/13/2023
Sublinear Algorithms for TSP via Path Covers
We study sublinear time algorithms for the traveling salesman problem (T...
share
research
∙
10/21/2022
Two-stage Stochastic Matching and Pricing with Applications to Ride Hailing
Matching and pricing are two critical levers in two-sided marketplaces t...
research
∙
06/27/2022
Beating Greedy Matching in Sublinear Time
We study sublinear time algorithms for estimating the size of maximum ma...
research
∙
05/18/2022
Improved Online Contention Resolution for Matchings and Applications to the Gig Economy
Motivated by applications in the gig economy, we study approximation alg...
research
∙
10/18/2021
Algorithms Using Local Graph Features to Predict Epidemics
We study a simple model of epidemics where an infected node transmits th...
research
∙
07/22/2021
The Stationary Prophet Inequality Problem
We study a continuous and infinite time horizon counterpart to the class...
research
∙
07/02/2021
Sequential importance sampling for estimating expectations over the space of perfect matchings
This paper makes three contributions to estimating the number of perfect...
research
∙
06/18/2021
Beating the Folklore Algorithm for Dynamic Matching
The maximum matching problem in dynamic graphs subject to edge updates (...
research
∙
06/12/2021
Decentralized Matching in a Probabilistic Environment
We consider a model for repeated stochastic matching where compatibility...
research
∙
05/14/2021
The Greedy Algorithm is not Optimal for On-Line Edge Coloring
Nearly three decades ago, Bar-Noy, Motwani and Naor showed that no onlin...
research
∙
04/07/2021
The Value of Excess Supply in Spatial Matching Markets
We study dynamic matching in a spatial setting. Drivers are distributed ...
research
∙
03/17/2021
Locality of Random Digraphs on Expanders
We study random digraphs on sequences of expanders with bounded average ...
research
∙
02/20/2021
Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities
The rich literature on online Bayesian selection problems has long focus...
research
∙
12/17/2020
Sampling Arborescences in Parallel
We study the problem of sampling a uniformly random directed rooted span...
research
∙
09/25/2020
Online Hypergraph Matching with Delays
We study an online hypergraph matching problem with delays, motivated by...
research
∙
02/21/2020
Ranking an Assortment of Products via Sequential Submodular Optimization
We study an optimization problem capturing a core operational question f...
research
∙
10/28/2018
Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neurons
We analyze linear independence of rank one tensors produced by tensor po...
research
∙
10/10/2018
Assignment Mechanisms under Distributional Constraints
We study the assignment problem of objects to agents with heterogeneous ...
research
∙
10/04/2018
Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications
In this paper we provide nearly linear time algorithms for several probl...
research
∙
08/09/2018
Maximum Weight Online Matching with Deadlines
We study the problem of matching agents who arrive at a marketplace over...
research
∙
07/15/2018
Nearly Optimal Pricing Algorithms for Production Constrained and Laminar Bayesian Selection
We study online pricing algorithms for the Bayesian selection problem wi...
research
∙
03/04/2018
Maximizing Efficiency in Dynamic Matching Markets
We study the problem of matching agents who arrive at a marketplace over...
research
∙
02/24/2017