47 citations · 236 across the 38 of their papers we have counts for
29 papers · 1 filter
Improved Bi-point Rounding Algorithms and a Golden Barrier for -Median
Kishen N. Gowda, Thomas Pensyl, Aravind Srinivasan +1
The current best approximation algorithms for -median rely on first obtaining a structured fractional solution known as a bi-point solution, and then rounding it to an integer s…
Controlling Epidemic Spread using Probabilistic Diffusion Models on Networks
Amy Babay, Michael Dinitz, Aravind Srinivasan +2
The spread of an epidemic is often modeled by an SIR random process on a social network graph. The MinINF problem for optimal social distancing involves minimizing the expected num…
Improved Guarantees for Offline Stochastic Matching via New Ordered Contention Resolution Schemes
Brian Brubach, Nathaniel Grammel, Will Ma +2
Matching is one of the most fundamental and broadly applicable problems across many domains. In these diverse real-world applications, there is often a degree of uncertainty in the…
Fair Disaster Containment via Graph-Cut Problems
Michael Dinitz, Aravind Srinivasan, Leonidas Tsepenekas +1
Graph cut problems are fundamental in Combinatorial Optimization, and are a central object of study in both theory and practice. Furthermore, the study of \emph{fairness} in Algori…
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…
Stochastic Optimization and Learning for Two-Stage Supplier Problems
Brian Brubach, Nathaniel Grammel, David G. Harris +3
The main focus of this paper is radius-based (supplier) clustering in the two-stage stochastic setting with recourse, where the inherent stochasticity of the model comes in the for…
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…
Online Matching Frameworks under Stochastic Rewards, Product Ranking, and Unknown Patience
Brian Brubach, Nathaniel Grammel, Will Ma +1
We study generalizations of online bipartite matching in which each arriving vertex (customer) views a ranked list of offline vertices (products) and matches to (purchases) the fir…
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…
Approximation algorithms for stochastic clustering
David G. Harris, Shi Li, Thomas Pensyl +2
We consider stochastic settings for clustering, and develop provably-good approximation algorithms for a number of these notions. These algorithms yield better approximation ratios…
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…
Approximation algorithms for stochastic and risk-averse optimization
Jaroslaw Byrka, Aravind Srinivasan
We present improved approximation algorithms in stochastic optimization. We prove that the multi-stage stochastic versions of covering integer programs (such as set cover and verte…
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…
A Lottery Model for Center-type Problems With Outliers
David G. Harris, Thomas Pensyl, Aravind Srinivasan +1
In this paper, we give tight approximation algorithms for the -center and matroid center problems with outliers. Unfairness arises naturally in this setting: certain clients cou…
Dependent randomized rounding for clustering and partition systems with knapsack constraints
David G. Harris, Thomas Pensyl, Aravind Srinivasan +1
Clustering problems are fundamental to unsupervised learning. There is an increased emphasis on fairness in machine learning and AI; one representative notion of fairness is that n…
Fairness in Resource Allocation and Slowed-down Dependent Rounding
David G. Harris, Thomas Pensyl, Aravind Srinivasan +1
We consider an issue of much current concern: could fairness, an issue that is already difficult to guarantee, worsen when algorithms run much of our lives? We consider this in the…
A constructive algorithm for the LLL on permutations
David G. Harris, Aravind Srinivasan
While there has been significant progress on algorithmic aspects of the Lovász Local Lemma (LLL) in recent years, a noteworthy exception is when the LLL is used in the context of r…
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…
Improved bounds and algorithms for graph cuts and network reliability
David G. Harris, Aravind Srinivasan
Karger (SIAM Journal on Computing, 1999) developed the first fully-polynomial approximation scheme to estimate the probability that a graph becomes disconnected, given that its…
Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines
Nikhil Bansal, Aravind Srinivasan, Ola Svensson
We consider the problem of scheduling jobs on unrelated machines so as to minimize the sum of weighted completion times. Our main result is a -approximation algorithm for…
Partial resampling to approximate covering integer programs
Antares Chen, David G. Harris, Aravind Srinivasan
We consider column-sparse covering integer programs, a generalization of set cover, which have a long line of research of (randomized) approximation algorithms. We develop a new ro…
An Improved Approximation for -median, and Positive Correlation in Budgeted Optimization
Jarosław Byrka, Thomas Pensyl, Bartosz Rybicki +2
Dependent rounding is a useful technique for optimization problems with hard budget constraints. This framework naturally leads to \emph{negative correlation} properties. However,…
On Computing Maximal Independent Sets of Hypergraphs in Parallel
Ioana O. Bercea, Navin Goyal, David G. Harris +1
Whether or not the problem of finding maximal independent sets (MIS) in hypergraphs is in (R)NC is one of the fundamental problems in the theory of parallel computing. Unlike the w…
LP-rounding algorithms for facility-location problems
Jaroslaw Byrka, MohammadReza Ghodsi, Aravind Srinivasan
We study LP-rounding approximation algorithms for metric uncapacitated facility-location problems. We first give a new analysis for the algorithm of Chudak and Shmoys, which differ…