34 citations · 150 across the 33 of their papers we have counts for
8 papers · 1 filter
Online minimum matching with uniform metric and random arrivals
Sharmila Duppala, Karthik A. Sankararaman, Pan Xu
We consider Online Minimum Bipartite Matching under the uniform metric. We show that Randomized Greedy achieves a competitive ratio equal to , which matches th…
Improved Approximation Algorithms for Stochastic-Matching Problems
Marek Adamczyk, Brian Brubach, Fabrizio Grandoni +3
We consider the Stochastic Matching problem, which is motivated by applications in kidney exchange and online dating. In this problem, we are given an undirected graph. Each edge i…
Mix and Match: Markov Chains & Mixing Times for Matching in Rideshare
Michael J. Curry, John P. Dickerson, Karthik Abinav Sankararaman +3
Rideshare platforms such as Uber and Lyft dynamically dispatch drivers to match riders' requests. We model the dispatching process in rideshare as a Markov chain that takes into ac…
Balancing Relevance and Diversity in Online Bipartite Matching via Submodularity
John P. Dickerson, Karthik Abinav Sankararaman, Aravind Srinivasan +1
In bipartite matching problems, vertices on one side of a bipartite graph are paired with those on the other. In its online variant, one side of the graph is available offline, whi…
Adversarial Bandits with Knapsacks
Nicole Immorlica, Karthik Abinav Sankararaman, Robert Schapire +1
We consider Bandits with Knapsacks (henceforth, BwK), a general model for multi-armed bandits under supply/budget constraints. In particular, a bandit algorithm needs to solve a we…
Attenuate Locally, Win Globally: An Attenuation-based Framework for Online Stochastic Matching with Timeouts
Brian Brubach, Karthik Abinav Sankararaman, Aravind Srinivasan +1
Online matching problems have garnered significant attention in recent years due to numerous applications in e-commerce, online advertisements, ride-sharing, etc. Many of them capt…
Algorithms to Approximate Column-Sparse Packing Problems
Brian Brubach, Karthik Abinav Sankararaman, Aravind Srinivasan +1
Column-sparse packing problems arise in several contexts in both deterministic and stochastic discrete optimization. We present two unifying ideas, (non-uniform) attenuation and mu…
Online Stochastic Matching: New Algorithms and Bounds
Brian Brubach, Karthik Abinav Sankararaman, Aravind Srinivasan +1
Online matching has received significant attention over the last 15 years due to its close connection to Internet advertising. As the seminal work of Karp, Vazirani, and Vazirani h…