Arrow Research search

Author name cluster

Aravind Srinivasan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

71 papers
2 author rows

Possible papers

71

NeurIPS Conference 2025 Conference Paper

Controlling The Spread of Epidemics on Networks with Differential Privacy

  • Dũng Nguyen
  • Aravind Srinivasan
  • Renata Valieva
  • Anil Vullikanti
  • Jiayi Wu

Designing effective strategies for controlling epidemic spread by vaccination is an important question in epidemiology, especially in the early stages when vaccines are limited. This is a challenging question when the contact network is very heterogeneous, and strategies based on controlling network properties, such as the degree and spectral radius, have been shown to be effective. Implementation of such strategies requires detailed information on the contact structure, which might be sensitive in many applications. Our focus here is on choosing effective vaccination strategies when the edges are sensitive and differential privacy guarantees are needed. Our main contributions are $(\varepsilon, \delta)$-differentially private algorithms for designing vaccination strategies by reducing the maximum degree and spectral radius. Our key technique is a private algorithm for the multi-set multi-cover problem, which we use for controlling network properties. We evaluate privacy-utility tradeoffs of our algorithms on multiple synthetic and real-world networks, and show their effectiveness.

PDF Details

AAAI Conference 2025 Conference Paper

Proportionally Fair Matching via Randomized Rounding

  • Sharmila Duppala
  • Nathaniel Grammel
  • Juan Luque
  • Calum MacRury
  • Aravind Srinivasan

Given an edge-colored graph, the goal of the proportional fair matching problem is to find a maximum weight matching while ensuring proportional representation (with respect to the number of edges) of each color. The colors may correspond to demographic groups or other protected traits where we seek to ensure roughly equal representation from each group. It is known that, assuming ETH, it is impossible to approximate the problem with ℓ colors in time subexponential in ℓ even on unweighted path graphs. Further, even determining the existence of a non-empty matching satisfying proportionality is NP-Hard. To overcome this hardness, we relax the stringent proportional fairness constraints to a probabilistic notion. We introduce a notion we call δ-PʀᴏʙᴀʙʟʏFᴀɪʀ where we ensure proportionality up to a factor of at most (1 ± δ) for some small δ > 0 with high probability. The violation δ can be brought arbitrarily close to 0 for some good instances with large values of matching size. We propose and analyze simple and fast algorithms for bipartite graphs that achieve constant-factor approximation guarantees, and return a δ-PʀᴏʙᴀʙʟʏFᴀɪʀ matching.

PDF Details DOI

ICML Conference 2024 Conference Paper

Promoting External and Internal Equities Under Ex-Ante/Ex-Post Metrics in Online Resource Allocation

  • Karthik Abinav Sankararaman
  • Aravind Srinivasan
  • Pan Xu 0001

This paper proposes two different models for equitable resource allocation in online settings. The first one is called external equity promotion, where sequentially arriving agents are heterogeneous in their external attributes, namely how many resources they demand, which are drawn from a probability distribution (accessible to the algorithm). The focus is then to devise an allocation policy such that every requester can get a fair share of resources proportional to their demands, regardless of their arrival time. The second is called internal equity promotion, where arriving requesters can be treated homogeneously in external attributes (demands) but are heterogeneous in internal traits such as demographics. In particular, each requester can be identified as belonging to one or several groups, and an allocation of resources is regarded as equitable when every group of requesters can receive a fair share of resources proportional to the percentage of that group in the whole population. For both models above, we consider as the benchmark a clairvoyant optimal solution that has the privilege to access all random demand realizations in advance. We consider two equity metrics, namely ex-post and ex-ante, and discuss the challenges under the two metrics in detail. Specifically, we present two linear program (LP)-based policies for external equity promotion under ex-ante with independent demands, each achieving an optimal CR of $1/2$ with respect to the benchmark LP. For internal equity promotion, we present optimal policies under both ex-ante and ex-post metrics.

Details

IJCAI Conference 2023 Conference Paper

Efficient and Equitable Deployment of Mobile Vaccine Distribution Centers

  • Da Qi Chen
  • Ann Li
  • George Z. Li
  • Madhav Marathe
  • Aravind Srinivasan
  • Leonidas Tsepenekas
  • Anil Vullikanti

Vaccines have proven to be extremely effective in preventing the spread of COVID-19 and potentially ending the pandemic. Lack of access caused many people not getting vaccinated early, so states such as Virginia deployed mobile vaccination sites in order to distribute vaccines across the state. Here we study the problem of deciding where these facilities should be placed and moved over time in order to minimize the distance each person needs to travel in order to be vaccinated. Traditional facility location models for this problem fail to incorporate the fact that our facilities are mobile (i. e. , they can move over time). To this end, we instead model vaccine distribution as the Dynamic k-Supplier problem and give the first approximation algorithms for this problem. We then run extensive simulations on real world datasets to show the efficacy of our methods. In particular, we find that natural baselines for Dynamic k-Supplier cannot take advantage of the mobility of the facilities, and perform worse than non-mobile k-Supplier algorithms.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

Group Fairness in Set Packing Problems

  • Sharmila Duppala
  • Juan Luque
  • John Dickerson
  • Aravind Srinivasan

Kidney exchange programs (KEPs) typically seek to match incompatible patient-donor pairs based on a utilitarian objective where the number or overall quality of transplants is maximized---implicitly penalizing certain classes of difficult to match (e. g. , highly-sensitized) patients. Prioritizing the welfare of highly-sensitized (hard-to-match) patients has been studied as a natural \textit{fairness} criterion. We formulate the KEP problem as $k$-set packing with a probabilistic group fairness notion of proportionality fairness---namely, fair $k$-set packing (\f{}). In this work we propose algorithms that take arbitrary proportionality vectors (i. e. , policy-informed demands of how to prioritize different groups) and return a probabilistically fair solution with provable guarantees. Our main contributions are randomized algorithms as well as hardness results for \f{} variants. Additionally, the tools we introduce serve to audit the price of fairness involved in prioritizing different groups in realistic KEPs and other $k$-set packing applications. We conclude with experiments on synthetic and realistic kidney exchange \textsc{FairSP} instances.

PDF Details DOI

SODA Conference 2023 Conference Paper

Improved Bi-point Rounding Algorithms and a Golden Barrier for k -Median

  • Kishen N. Gowda
  • Thomas W. Pensyl
  • Aravind Srinivasan
  • Khoa Trinh

The current best approximation algorithms for k -median rely on first obtaining a structured fractional solution known as a bi-point solution, and then rounding it to an integer solution. We improve this second step by unifying and refining previous approaches. We describe a hierarchy of increasingly-complex partitioning schemes for the facilities, along with corresponding sets of algorithms and factor-revealing non-linear programs. We prove that the third layer of this hierarchy is a 2. 613-approximation, improving upon the current best ratio of 2. 675, while no layer can be proved better than 2. 588 under the proposed analysis. On the negative side, we give a family of bi-point solutions which cannot be approximated better than the square root of the golden ratio, even if allowed to open k + o ( k ) facilities. This gives a barrier to current approaches for obtaining an approximation better than. Altogether we reduce the approximation gap of bi-point solutions by two thirds.

Details

AAAI Conference 2023 Conference Paper

Rawlsian Fairness in Online Bipartite Matching: Two-Sided, Group, and Individual

  • Seyed Esmaeili
  • Sharmila Duppala
  • Davidson Cheng
  • Vedant Nanda
  • Aravind Srinivasan
  • John P. Dickerson

Online bipartite-matching platforms are ubiquitous and find applications in important areas such as crowdsourcing and ridesharing. In the most general form, the platform consists of three entities: two sides to be matched and a platform operator that decides the matching. The design of algorithms for such platforms has traditionally focused on the operator’s (expected) profit. Since fairness has become an important consideration that was ignored in the existing algorithms a collection of online matching algorithms have been developed that give a fair treatment guarantee for one side of the market at the expense of a drop in the operator’s profit. In this paper, we generalize the existing work to offer fair treatment guarantees to both sides of the market simultaneously, at a calculated worst case drop to operator profit. We consider group and individual Rawlsian fairness criteria. Moreover, our algorithms have theoretical guarantees and have adjustable parameters that can be tuned as desired to balance the trade-off between the utilities of the three sides. We also derive hardness results that give clear upper bounds over the performance of any algorithm.

PDF Details DOI

JMLR Journal 2022 Journal Article

Dependent randomized rounding for clustering and partition systems with knapsack constraints

  • David G. Harris
  • Thomas Pensyl
  • Aravind Srinivasan
  • Khoa Trinh

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 no single group should be over-represented among the cluster-centers. This, and much more general clustering problems, can be formulated with “knapsack" and “partition" constraints. We develop new randomized algorithms targeting such problems, and study two in particular: multi-knapsack median and multi-knapsack center. Our rounding algorithms give new approximation and pseudo-approximation algorithms for these problems. One key technical tool, which may be of independent interest, is a new tail bound analogous to Feige (2006) for sums of random variables with unbounded variances. Such bounds can be useful in inferring properties of large networks using few samples. [abs] [ pdf ][ bib ] &copy JMLR 2022. ( edit, beta )

PDF Details

AAMAS Conference 2022 Conference Paper

Deploying Vaccine Distribution Sites for Improved Accessibility and Equity to Support Pandemic Response

  • George Z. Li
  • Ann Li
  • Madhav Marathe
  • Aravind Srinivasan
  • Leonidas Tsepenekas
  • Anil Vullikanti

In response to COVID-19, many countries have mandated social distancing and banned large group gatherings in order to slow down the spread of SARS-CoV-2. These social interventions along with vaccines remain the best way forward to reduce the spread of SARS CoV-2. In order to increase vaccine accessibility, states such as Virginia have deployed mobile vaccination centers to distribute vaccines across the state. When choosing where to place these sites, there are two important factors to take into account: accessibility and equity. We formulate a combinatorial problem that captures these factors and then develop efficient algorithms with theoretical guarantees on both of these aspects. Furthermore, we study the inherent hardness of the problem, and demonstrate strong impossibility results. Finally, we run computational experiments on real-world data to show the efficacy of our methods.

PDF

IJCAI Conference 2022 Conference Paper

Forecasting Patient Outcomes in Kidney Exchange

  • Naveen Durvasula
  • Aravind Srinivasan
  • John Dickerson

Kidney exchanges allow patients with end-stage renal disease to find a lifesaving living donor by way of an organized market. However, not all patients are equally easy to match, nor are all donor organs of equal quality---some patients are matched within weeks, while others may wait for years with no match offers at all. We propose the first decision-support tool for kidney exchange that takes as input the biological features of a patient-donor pair, and returns (i) the probability of being matched prior to expiry, and (conditioned on a match outcome), (ii) the waiting time for and (iii) the organ quality of the matched transplant. This information may be used to inform medical and insurance decisions. We predict all quantities (i, ii, iii) exclusively from match records that are readily available in any kidney exchange using a quantile random forest approach. To evaluate our approach, we developed two state-of-the-art realistic simulators based on data from the United Network for Organ Sharing that sample from the training and test distribution for these learning tasks---in our application these distributions are distinct. We analyze distributional shift through a theoretical lens, and show that the two distributions converge as the kidney exchange nears steady-state. We then show that our approach produces clinically-promising estimates using simulated data. Finally, we show how our approach, in conjunction with tools from the model explainability literature, can be used to calibrate and detect bias in matching policies.

PDF Details DOI

AAMAS Conference 2022 Conference Paper

Rawlsian Fairness in Online Bipartite Matching: Two-sided, Group, and Individual

  • Seyed A. Esmaeili
  • Sharmila Duppala
  • Vedant Nanda
  • Aravind Srinivasan
  • John P. Dickerson

Online bipartite-matching platforms are ubiquitous and find applications in important areas such as crowdsourcing and ridesharing. In the most general form, the platform consists of three entities: two sides to be matched and a platform operator that decides the matching. The design of algorithms for such platforms has traditionally focused on the operator’s (expected) profit. Recent reports have shown that certain demographic groups may receive less favorable treatment under pure profit maximization. As a result, a collection of online matching algorithms have been developed that give a fair treatment guarantee for one side of the market at the expense of a drop in the operator’s profit. In this paper, we generalize the existing work to offer fair treatment guarantees to both sides of the market simultaneously, at a calculated worst case drop to operator profit. We consider group and individual Rawlsian fairness criteria. Moreover, our algorithms have theoretical guarantees and have adjustable parameters that can be tuned as desired to balance the trade-off between the utilities of the three sides. We also derive hardness results that give clear upper bounds over the performance of any algorithm.

PDF

AAMAS Conference 2022 Conference Paper

The Generalized Magician Problem under Unknown Distributions and Related Applications

  • Aravind Srinivasan
  • Pan Xu

The Magician Problem (MP) and its generalization, the Generalized Magician Problem (GMP), were introduced by Alaei et al. (APPROX- RANDOM 2013) and Alaei (SICOMP 2014) and have been used as powerful ingredients in online-algorithm design for many hard problems such as the k-choice prophet inequality, mechanism design in Bayesian combinatorial auctions, and the generalized assignment problem. The adversarial model here is essentially that of an oblivious adversary. In this paper, we introduce generalizations of GMP (MP) under two different arrival settings (by making the adversary stronger): unknown independent identical distributions (UIID) and unknown adversarial distributions (UAD). Different adversary models capture a range of arrival patterns. For GMP under UIID, we show that a natural greedy algorithm Greedy is optimal. For the case of MP under UIID, we show that Greedy has an optimal performance of 1 − BB B! eB ≥ 1 − 1 √ 2π B, where B is the budget, and show an application to online B-matching with stochastic rewards. For GMP under UAD, we present a simple algorithm, which is near-optimal among all non-adaptive algorithms. We consider the simple case of MP under UAD with B = 1, and give an exact characterization of the respective optimal adaptive and optimal non-adaptive algorithms for any finite time horizon. We offer an example of MP under UAD on which there is a provable gap between the classical MP under adversarial order and MP under UAD even with a time horizon T = 4.

PDF

AAMAS Conference 2022 Conference Paper

Theoretical Models and Preliminary Results for Contact Tracing and Isolation

  • George Z. Li
  • Arash Haddadan
  • Ann Li
  • Madhav V. Marathe
  • Aravind Srinivasan
  • Anil Vullikanti
  • Zeyu Zhao

Efficient contact tracing and isolation is an effective strategy to control epidemics, as seen in the Ebola epidemic and COVID-19 pandemic. An important consideration in contact tracing is the budget on the number of individuals asked to quarantine—the budget is limited for socioeconomic reasons (e. g. , having a limited number of contact tracers). Here, we present a Markov Decision Process (MDP) framework to formulate the problem of using contact tracing to reduce the size of an outbreak while limiting the number of people quarantined. We formulate each step of the MDP as a combinatorial problem, MinExposed, which we demonstrate is NP-Hard. Next, we develop two approximation algorithms, one based on rounding the solutions of a linear program and another (greedy algorithm) based on choosing nodes with a high (weighted) degree. A key feature of the greedy algorithm is that it does not need complete information of the underlying social contact network, making it implementable in practice. Using simulations over realistic networks, we show how the algorithms can help in bending the epidemic curve with a limited number of isolated individuals.

PDF

NeurIPS Conference 2021 Conference Paper

Fair Clustering Under a Bounded Cost

  • Seyed Esmaeili
  • Brian Brubach
  • Aravind Srinivasan
  • John Dickerson

Clustering is a fundamental unsupervised learning problem where a dataset is partitioned into clusters that consist of nearby points in a metric space. A recent variant, fair clustering, associates a color with each point representing its group membership and requires that each color has (approximately) equal representation in each cluster to satisfy group fairness. In this model, the cost of the clustering objective increases due to enforcing fairness in the algorithm. The relative increase in the cost, the ```````''price of fairness, '' can indeed be unbounded. Therefore, in this paper we propose to treat an upper bound on the clustering objective as a constraint on the clustering problem, and to maximize equality of representation subject to it. We consider two fairness objectives: the group utilitarian objective and the group egalitarian objective, as well as the group leximin objective which generalizes the group egalitarian objective. We derive fundamental lower bounds on the approximation of the utilitarian and egalitarian objectives and introduce algorithms with provable guarantees for them. For the leximin objective we introduce an effective heuristic algorithm. We further derive impossibility results for other natural fairness objectives. We conclude with experimental results on real-world datasets that demonstrate the validity of our algorithms.

PDF Details

AAAI Conference 2021 Conference Paper

Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraints

  • Brian Brubach
  • Darshan Chakrabarti
  • John P. Dickerson
  • Aravind Srinivasan
  • Leonidas Tsepenekas

Metric clustering is fundamental in areas ranging from Combinatorial Optimization and Data Mining, to Machine Learning and Operations Research. However, in a variety of situations we may have additional requirements or knowledge, distinct from the underlying metric, regarding which pairs of points should be clustered together. To capture and analyze such scenarios, we introduce a novel family of stochastic pairwise constraints, which we incorporate into several essential clustering objectives (radius/median/means). Moreover, we demonstrate that these constraints can succinctly model an intriguing collection of applications, including among others Individual Fairness in clustering and Must-link constraints in semi-supervised learning. Our main result consists of a general framework that yields approximation algorithms with provable guarantees for important clustering objectives, while at the same time producing solutions that respect the stochastic pairwise constraints. Furthermore, for certain objectives we devise improved results in the case of Must-link constraints, which are also the best possible from a theoretical perspective. Finally, we present experimental evidence that validates the effectiveness of our algorithms.

PDF Details

NeurIPS Conference 2021 Conference Paper

Improved Guarantees for Offline Stochastic Matching via new Ordered Contention Resolution Schemes

  • Brian Brubach
  • Nathaniel Grammel
  • Will Ma
  • Aravind Srinivasan

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 input which has led to the study of stochastic matching models. Here, each edge in the graph has a known, independent probability of existing derived from some prediction. Algorithms must probe edges to determine existence and match them irrevocably if they exist. Further, each vertex may have a patience constraint denoting how many of its neighboring edges can be probed. We present new ordered contention resolution schemes yielding improved approximation guarantees for some of the foundational problems studied in this area. For stochastic matching with patience constraints in general graphs, we provide a $0. 382$-approximate algorithm, significantly improving over the previous best $0. 31$-approximation of Baveja et al. (2018). When the vertices do not have patience constraints, we describe a $0. 432$-approximate random order probing algorithm with several corollaries such as an improved guarantee for the Prophet Secretary problem under Edge Arrivals. Finally, for the special case of bipartite graphs with unit patience constraints on one of the partitions, we show a $0. 632$-approximate algorithm that improves on the recent $1/3$-guarantee of Hikima et al. (2021).

PDF Details

ICML Conference 2020 Conference Paper

A Pairwise Fair and Community-preserving Approach to k-Center Clustering

  • Brian Brubach
  • Darshan Chakrabarti
  • John Dickerson 0001
  • Samir Khuller
  • Aravind Srinivasan
  • Leonidas Tsepenekas

Clustering is a foundational problem in machine learning with numerous applications. As machine learning increases in ubiquity as a backend for automated systems, concerns about fairness arise. Much of the current literature on fairness deals with discrimination against protected classes in supervised learning (group fairness). We define a different notion of fair clustering wherein the probability that two points (or a community of points) become separated is bounded by an increasing function of their pairwise distance (or community diameter). We capture the situation where data points represent people who gain some benefit from being clustered together. Unfairness arises when certain points are deterministically separated, either arbitrarily or by someone who intends to harm them as in the case of gerrymandering election districts. In response, we formally define two new types of fairness in the clustering setting, pairwise fairness and community preservation. To explore the practicality of our fairness goals, we devise an approach for extending existing $k$-center algorithms to satisfy these fairness constraints. Analysis of this approach proves that reasonable approximations can be achieved while maintaining fairness. In experiments, we compare the effectiveness of our approach to classical $k$-center algorithms/heuristics and explore the tradeoff between optimal clustering and fairness.

Details

AAAI Conference 2020 Conference Paper

Balancing the Tradeoff between Profit and Fairness in Rideshare Platforms during High-Demand Hours

  • Vedant Nanda
  • Pan Xu
  • Karthik Abhinav Sankararaman
  • John Dickerson
  • Aravind Srinivasan

Rideshare platforms, when assigning requests to drivers, tend to maximize profit for the system and/or minimize waiting time for riders. Such platforms can exacerbate biases that drivers may have over certain types of requests. We consider the case of peak hours when the demand for rides is more than the supply of drivers. Drivers are well aware of their advantage during the peak hours and can choose to be selective about which rides to accept. Moreover, if in such a scenario, the assignment of requests to drivers (by the platform) is made only to maximize profit and/or minimize wait time for riders, requests of a certain type (e. g. , from a non-popular pickup location, or to a non-popular drop-off location) might never be assigned to a driver. Such a system can be highly unfair to riders. However, increasing fairness might come at a cost of the overall profit made by the rideshare platform. To balance these conflicting goals, we present a flexible, nonadaptive algorithm, NAdap, that allows the platform designer to control the profit and fairness of the system via parameters α and β respectively. We model the matching problem as an online bipartite matching where the set of drivers is of- fline and requests arrive online. Upon the arrival of a request, we use NAdap to assign it to a driver (the driver might then choose to accept or reject it) or reject the request. We formalize the measures of profit and fairness in our setting and show that by using NAdap, the competitive ratios for profit and fairness measures would be no worse than α/e and β/e respectively. Extensive experimental results on both real-world and synthetic datasets confirm the validity of our theoretical lower bounds. Additionally, they show that NAdap under some choice of (α, β) can beat two natural heuristics, Greedy and Uniform, on both fairness and profit. Code is available at: https: //github. com/nvedant07/rideshare-fairness-peak/.

PDF Details

AAAI Conference 2019 Conference Paper

A Unified Approach to Online Matching with Conflict-Aware Constraints

  • Pan Xu
  • Yexuan Shi
  • Hao Cheng
  • John Dickerson
  • Karthik Abinav Sankararaman
  • Aravind Srinivasan
  • Yongxin Tong
  • Leonidas Tsepenekas

Online bipartite matching and allocation models are widely used to analyze and design markets such as Internet advertising, online labor, and crowdsourcing. Traditionally, vertices on one side of the market are fixed and known a priori, while vertices on the other side arrive online and are matched by a central agent to the offline side. The issue of possible conflicts among offline agents emerges in various real scenarios when we need to match each online agent with a set of offline agents. For example, in event-based social networks (e. g. , Meetup), offline events conflict for some users since they will be unable to attend mutually-distant events at proximate times; in advertising markets, two competing firms may prefer not to be shown to one user simultaneously; and in online recommendation systems (e. g. , Amazon Books), books of the same type “conflict” with each other in some sense due to the diversity requirement for each online buyer. The conflict nature inherent among certain offline agents raises significant challenges in both modeling and online algorithm design. In this paper, we propose a unifying model, generalizing the conflict models proposed in (She et al. , TKDE 2016) and (Chen et al. , TKDE 16). Our model can capture not only a broad class of conflict constraints on the offline side (which is even allowed to be sensitive to each online agent), but also allows a general arrival pattern for the online side (which is allowed to change over the online phase). We propose an efficient linear programming (LP) based online algorithm and prove theoretically that it has nearly-optimal online performance. Additionally, we propose two LP-based heuristics and test them against two natural baselines on both real and synthetic datasets. Our LP-based heuristics experimentally dominate the baseline algorithms, aligning with our theoretical predictions and supporting our unified approach.

PDF Details

JMLR Journal 2019 Journal Article

Approximation Algorithms for Stochastic Clustering

  • David G. Harris
  • Shi Li
  • Thomas Pensyl
  • Aravind Srinivasan
  • Khoa Trinh

We consider stochastic settings for clustering, and develop provably-good approximation algorithms for a number of these notions. These algorithms yield better approximation ratios compared to the usual deterministic clustering setting. Additionally, they offer a number of advantages including clustering which is fairer and has better long-term behavior for each user. In particular, they ensure that every user is guaranteed to get good service (on average). We also complement some of these with impossibility results. [abs] [ pdf ][ bib ] &copy JMLR 2019. ( edit, beta )

PDF Details

AAAI Conference 2019 Conference Paper

Balancing Relevance and Diversity in Online Bipartite Matching via Submodularity

  • John P. Dickerson
  • Karthik Abinav Sankararaman
  • Aravind Srinivasan
  • Pan Xu

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, while the vertices on the other side arrive online. When a vertex arrives, an irrevocable and immediate decision should be made by the algorithm; either match it to an available vertex or drop it. Examples of such problems include matching workers to firms, advertisers to keywords, organs to patients, and so on. Much of the literature focuses on maximizing the total relevance—modeled via total weight—of the matching. However, in many real-world problems, it is also important to consider contributions of diversity: hiring a diverse pool of candidates, displaying a relevant but diverse set of ads, and so on. In this paper, we propose the Online Submodular Bipartite Matching (OSBM) problem, where the goal is to maximize a submodular function f over the set of matched edges. This objective is general enough to capture the notion of both diversity (e. g. , a weighted coverage function) and relevance (e. g. , the traditional linear function)—as well as many other natural objective functions occurring in practice (e. g. , limited total budget in advertising settings). We propose novel algorithms that have provable guarantees and are essentially optimal when restricted to various special cases. We also run experiments on real-world and synthetic datasets to validate our algorithms.

PDF Details

AAMAS Conference 2019 Conference Paper

Online Resource Allocation with Matching Constraints

  • John P. Dickerson
  • Karthik Abinav Sankararaman
  • Kanthi Kiran Sarpatwar
  • Aravind Srinivasan
  • Kun-Lung Wu
  • Pan Xu

Matching markets with historical data are abundant in many applications, e. g. , matching candidates to jobs in hiring, workers to tasks in crowdsourcing markets, and jobs to servers in cloud services. In all these applications, a match consumes one or more shared and limited resources and the goal is to best utilize these to maximize a global objective. Additionally, one often has historical data and hence some statistics (usually first-order moments) of the arriving agents (e. g. , candidates, workers, and jobs) can be learnt. To model these scenarios, we propose a unifying framework, called Multi- Budgeted Online Assignment with Known Adversarial Distributions. In this model, we have a set of offline servers with different deadlines and a set of online job types. At each time, a job of type j arrives. Assigning this job to a server i yields a profit wi, j while consuming ae ∈ [0, 1]K quantities of distinct resources. The goal is to design an (online) assignment policy that maximizes the total expected profit without violating the (hard) budget constraint. We propose and theoretically analyze two linear programming (LP) based algorithms which are almost optimal among all LP-based approaches. We also propose several heuristics adapted from our algorithms and compare them to other LP-agnostic algorithms using both synthetic as well as real-time cloud scheduling and public safety datasets. Experimental results show that our proposed algorithms are effective and significantly out-perform the baselines. Moreover, we show empirically the trade-off between fairness and efficiency of our algorithms which does well even on fairness metrics without explicitly optimizing for it. ∗Part of this work is done when Pan Xu was an intern at the IBM T. J. Watson Research Center during the summer of 2016. Aravind Srinivasan’s research was supported in part by NSF Awards CNS-1010789, CCF-1422569 and CCF-1749864, and by research awards from Adobe, Inc. Karthik Sankararaman’s research was supported in part by NSF Awards CNS-1010789 and CCF-1422569. John Dickerson’s research was supported by NSF IIS RI CAREER Award #1846237. Pan Xu’s research was supported by NSF Awards CNS-1010789, CCF-1422569 and NSF IIS RI CAREER Award #1846237. The authors also like to thank Google for a generous gift support. We thank Aditya Parameswaran and Xingjie Liu for useful discussions on datasets related to our problem. Proc. of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019), N. Agmon, M. E. Taylor, E. Elkind, M. Veloso (eds.), May 13–17, 2019, Montreal, Canada. © 2019 International Foundation for Autonomous Agents and Multiagent Systems (www. ifaamas. org). All rights reserved.

PDF

SODA Conference 2018 Conference Paper

Algorithms to Approximate Column-Sparse Packing Problems

  • Brian Brubach
  • Karthik Abinav Sankararaman
  • Aravind Srinivasan
  • Pan Xu 0001

Column-sparse packing problems arise in several contexts in both deterministic and stochastic discrete optimization. We present two unifying ideas, (non-uniform) attenuation and multiple-chance algorithms, to obtain improved approximation algorithms for some well-known families of such problems. As three main examples, we attain the integrality gap, up to lower-order terms, for known LP relaxations for k -column sparse packing integer programs (Bansal et al. , Theory of Computing, 2012) and stochastic k -set packing (Bansal et al. , Algorithmica, 2012), and go “half the remaining distance” to optimal for a major integrality-gap conjecture of Füredi, Kahn and Seymour on hypergraph matching ( Combinatorica, 1993).

Details

AAAI Conference 2018 Conference Paper

Allocation Problems in Ride-Sharing Platforms: Online Matching With Offline Reusable Resources

  • John Dickerson
  • Karthik Sankararaman
  • Aravind Srinivasan
  • Pan Xu

Bipartite matching markets pair agents on one side of a market with agents, items, or contracts on the opposing side. Prior work addresses online bipartite matching markets, where agents arrive over time and are dynamically matched to a known set of disposable resources. In this paper, we propose a new model, Online Matching with (offline) Reusable Resources under Known Adversarial Distributions (OM-RR-KAD), in which resources on the offline side are reusable instead of disposable; that is, once matched, resources become available again at some point in the future. We show that our model is tractable by presenting an LP-based adaptive algorithm that achieves an online competitive ratio of 1 2 − for any given > 0. We also show that no non-adaptive algorithm can achieve a ratio of 1 2 + o(1) based on the same benchmark LP. Through a data-driven analysis on a massive openly-available dataset, we show our model is robust enough to capture the application of taxi dispatching services and ridesharing systems. We also present heuristics that perform well in practice.

PDF Details

NeurIPS Conference 2018 Conference Paper

Approximation algorithms for stochastic clustering

  • David Harris
  • Shi Li
  • Aravind Srinivasan
  • Khoa Trinh
  • Thomas Pensyl

We consider stochastic settings for clustering, and develop provably-good (approximation) algorithms for a number of these notions. These algorithms allow one to obtain better approximation ratios compared to the usual deterministic clustering setting. Additionally, they offer a number of advantages including providing fairer clustering and clustering which has better long-term behavior for each user. In particular, they ensure that every user is guaranteed to get good service (on average). We also complement some of these with impossibility results.

PDF Details

AAMAS Conference 2018 Conference Paper

Assigning Tasks to Workers based on Historical Data: Online Task Assignment with Two-sided Arrivals

  • John P. Dickerson
  • Karthik Abinav Sankararaman
  • Aravind Srinivasan
  • Pan Xu

Efficient allocation of tasks to workers is a central problem in crowdsourcing. In this paper, we consider a special setting inspired from spatial crowdsourcing platforms where both workers and tasks arrive dynamically. Additionally, we assume all tasks are heterogeneous and each worker-task assignment brings a distinct reward. The natural challenge lies in how to incorporate the uncertainty in the arrivals from both workers and tasks into our online allocation policy such that the total expected rewards are maximized. To attack this challenge, we assume the arrival patterns of worker “types” and task “types” are not erratic and can be predicted from historical data. To be more specific, we consider a finite time horizon T and assume in each time-step, a single worker and task are sampled (i. e. , “arrive”) from two respective distributions independently, and this sampling process repeats identically and independently for the entire T online time-steps. Our model, called Online Task Assignment with Two-Sided Arrival (OTA-TSA), is a significant generalization of the classical online task assignment where the set of tasks is assumed to be available offline. For the general version of OTA-TSA, we present an optimal non-adaptive algorithm which achieves an online competitive ratio of 0. 295. For the special case of OTA-TSA where the reward is a function of just the worker type, we present an improved algorithm (which is adaptive) and achieves a competitive ratio of at least 0. 343. On the hardness side, along with showing that the ratio obtained by our non-adaptive algorithm is the best possible among all nonadaptive algorithms, we further show that no (adaptive) algorithm can achieve a ratio better than 0. 581 (unconditionally), even for the special case of OTA-TSA with homogenous tasks (i. e. , all rewards are same). At the heart of our analysis lies a new technical tool (which is a refined notion of the birth-death process), called the two-stage birth-death process, which may be of independent interest. Finally, we perform numerical experiments on two real-world datasets obtained from crowdsourcing platforms to complement our theoretical results.

PDF

AAMAS Conference 2017 Conference Paper

Attenuate Locally, Win Globally: An Attenuation-based Framework for Online Stochastic Matching with Timeouts

  • Brian Brubach
  • Karthik Abinav Sankararaman
  • Aravind Srinivasan
  • Pan Xu

Online matching problems have garnered significant attention in recent years due to numerous applications. Many of them capture the uncertainty in the real world by including stochasticity in both the arrival process and the matching process. The Online Stochastic Matching with Timeouts problem introduced by Bansal, Gupta, Li, Mestre, Nagarajan, and Rudra (Algorithmica, 2012) models matching markets (e. g. E-Bay, Amazon). Buyers arrive from an independent and identically distributed (i. i. d.) known distribution on buyer profiles and can be shown a list of items one at a time. Each buyer has some probability of purchasing each item and a limit (timeout) on the number of items they can be shown. Bansal et al. (Algorithmica, 2012) gave a 0. 12-competitive algorithm which was improved by Adamczyk, Grandoni, and Mukherjee (ESA, 2015) to 0. 24. We present an online attenuation framework that uses an algorithm for offline stochastic matching as a black box. Our main contributions are as follows. On the upper bound side, we show that this framework combined with a black box adapted from Bansal et al. (Algorithmica, 2012) yields an online algorithm which nearly doubles the ratio to 0. 46. On the lower bound side, we show that no algorithm can achieve a ratio better than 0. 632 using the common LP for this problem. This framework has a high potential for further improvements since new algorithms for offline stochastic matching can lead directly to improvements for the online problem. Our online framework also has the potential for a variety of extensions. For example, we introduce a natural generalization: Online Stochastic Matching with Two-sided Timeouts in which both online and offline vertices have timeouts. Our framework provides the first algorithm for this problem achieving a ratio of 0. 31. We accomplish this by proposing a new black box algorithm for offline stochastic matching on star graphs, which may be of independent interest. This new black box improves the approximation ratio for ∗For detailed proofs, refer the full version of the paper. Aravind Srinivasan’s research was supported in part by NSF Awards CNS-1010789 and CCF-1422569, and by a research award from Adobe, Inc. The research of Brian Brubach, Karthik Sankararaman, and Pan Xu was supported in part by NSF Awards CNS-1010789 and CCF-1422569. Appears in: Proc. of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2017), S. Das, E. Durfee, K. Larson, M. Winikoff (eds.), May 8–12, 2017, São Paulo, Brazil. Copyright © 2017, International Foundation for Autonomous Agents and Multiagent Systems (www. ifaamas. org). All rights reserved. the offline stochastic matching problem on star graphs from 0. 5 by Adamczyk et al. (ESA 2015) to 0. 56.

PDF

SODA Conference 2016 Conference Paper

Partial Resampling to Approximate Covering Integer Programs

  • Antares Chen
  • David G. Harris 0001
  • Aravind Srinivasan

We consider positive covering integer programs, which generalize set cover and which have attracted a long line of research developing (randomized) approximation algorithms. Srinivasan (2006) gave a rounding algorithm based on the FKG inequality for systems which are “column-sparse. ” This algorithm may return an integer solution in which the variables get assigned large (integral) values; Kolliopoulos & Young (2005) modified this algorithm to limit the solution size, at the cost of a worse approximation ratio. We develop a new rounding scheme based on the Partial Resampling variant of the Lovász Local Lemma developed by Harris & Srinivasan (2013). This achieves an approximation ratio of, where a min is the minimum covering constraint and Δ 1 is the maximum ℓ 1 -norm of any column of the covering matrix (whose entries are scaled to lie in [0, 1]); we also show nearly-matching inapproximability and integrality-gap lower bounds. Our approach improves asymptotically, in several different ways, over known results. First, it replaces Δ 0, the maximum number of nonzeroes in any column (from the result of Srinivasan) by Δ 1 which is always – and can be much – smaller than Δ 0; this is the first such result in this context. Second, our algorithm automatically handles multi-criteria programs; we achieve improved approximation ratios compared to the algorithm of Srinivasan, and give, for the first time when the number of objective functions is large, polynomial-time algorithms with good multi-criteria approximations. We also significantly improve upon the upper-bounds of Kolliopoulos & Young when the integer variables are required to be within (1 + ∊) of some given upper-bounds, and show nearly-matching inapproximability.

Details

IS Journal 2015 Journal Article

Model-Based Forecasting of Significant Societal Events

  • Naren Ramakrishnan
  • Chang-Tien Lu
  • Madhav Marathe
  • Achla Marathe
  • Anil Vullikanti
  • Stephen Eubank
  • Scotland Leman
  • Michael Roan

The article outlines some salient aspects of Embers-generated forecasts through its design considerations, system architecture, and user interface.

Details DOI

SODA Conference 2014 Conference Paper

Improved bounds and algorithms for graph cuts and network reliability

  • David G. Harris 0001
  • Aravind Srinivasan

Karger ( SIAM Journal on Computing, 1999) developed the first fully-polynomial approximation scheme to estimate the probability that a graph G becomes disconnected, given that its edges are removed independently with probability p. This algorithm runs in O ( n 5+ o (1) ∊ −3 ) time to obtain an estimate within relative error ∊. We improve this runtime in two key ways, one algorithmic and one graph-theoretic. From an algorithmic point of view, there is a certain key sub-problem encountered by Karger, for which a generic estimation procedure is employed. We show that this sub-problem has a special structure for which a much more efficient algorithm can be used. From a graph-theoretic point of view, we show better bounds on the number of edge cuts which are likely to fail. Karger's analysis depends on bounds for various graph parameters; we show that these bounds cannot be simultaneously tight. We describe a new graph parameter, which simultaneously influences all the bounds used by Karger, and use it to obtain much tighter estimates of the behavior of the cuts of G. These techniques allow us to improve the runtime to n 3+ o (1) ∊ −2, which is essentially best-possible for the meta-approach proposed by Karger; our results also rigorously prove certain experimental observations of Karger & Tai ( Proc. ACM-SIAM Symposium on Discrete Algorithms, 1997). A key driver of Karger's approach (and other cut-related results) is his earlier bound on the number of small cuts: we also show how to improve this when the min-cut size is “small” and odd, augmenting, in part, a result of Bixby ( Bull. AMS, 1974).

Details

FOCS Conference 2013 Conference Paper

The Moser-Tardos Framework with Partial Resampling

  • David G. Harris 0001
  • Aravind Srinivasan

The resampling algorithm of Moser & Tardos is a powerful approach to develop versions of the Lovasz Local Lemma. We develop a partial resampling approach motivated by this methodology: when a bad event holds, we resample an appropriately-random subset of the set of variables that define this event, rather than the entire set as in Moser & Tardos. This leads to several improved algorithmic applications in scheduling, graph transversals, packet routing etc. For instance, we improve the approximation ratio of a generalized D-dimensional scheduling problem studied by Azar & Epstein from O(D) to O(log D/ log log D), and settle a conjecture of Szabo & Tardos on graph transversals asymptotically.

Details

FOCS Conference 2010 Conference Paper

New Constructive Aspects of the Lovasz Local Lemma

  • Bernhard Haeupler
  • Barna Saha
  • Aravind Srinivasan

The Lovász Local Lemma (LLL) is a powerful tool that gives sufficient conditions for avoiding all of a given set of "bad" events, with positive probability. A series of results have provided algorithms to efficiently construct structures whose existence is non-constructively guaranteed by the LLL, culminating in the recent breakthrough of Moser & Tardos. We show that the output distribution of the Moser-Tardos algorithm well-approximates the conditional LLL-distribution - the distribution obtained by conditioning on all bad events being avoided. We show how a known bound on the probabilities of events in this distribution can be used for further probabilistic analysis and give new constructive and non-constructive results. We also show that when an LLL application provides a small amount of slack, the number of resamplings of the Moser-Tardos algorithm is nearly linear in the number of underlying independent variables (not events!), and can thus be used to give efficient constructions in cases where the underlying proof applies the LLL to super-polynomially many events. Even in cases where finding a bad event that holds is computationally hard, we show that applying the algorithm to avoid a polynomial-sized "core" subset of bad events leads to a desired outcome with high probability. We demonstrate this idea on several applications. We give the first constant-factor approximation algorithm for the Santa Claus problem by making an LLL-based proof of Feige constructive. We provide Monte Carlo algorithms for acyclic edge coloring, non-repetitive graph colorings, and Ramsey-type graphs. In all these applications the algorithm falls directly out of the non-constructive LLL-based proof. Our algorithms are very simple, often provide better bounds than previous algorithms, and are in several cases the first efficient algorithms known. As a second type of application we consider settings beyond the critical dependency threshold of the LLL: avoiding all bad events is impossible in these cases. As the first (even non-constructive) result of this kind, we show that by sampling from the LLL-distribution of a selected smaller core, we can avoid a fraction of bad events that is higher than the expectation. MAX k-SAT is an example of this.

Details

FOCS Conference 2005 Conference Paper

Approximation Algorithms for Scheduling on Multiple Machines

  • V. S. Anil Kumar 0001
  • Madhav V. Marathe
  • Srinivasan Parthasarathy 0002
  • Aravind Srinivasan

We develop a single rounding algorithm for scheduling on unrelated parallel machines; this algorithm works well with the known linear programming, quadratic programming, and convex programming-relaxations for scheduling to minimize completion time, makespan, and other well-studied objective functions. We obtain the following applications for the general setting of unrelated parallel machines: (i) a bicriteria algorithm for a schedule whose weighted completion-time and makespan simultaneously exhibit the current-best individual approximations for these criteria (3/2 and 2, respectively); (ii) better-than-two approximation guarantees for scheduling under the L/sub p/ norm for all 1 < p < /spl infin/, improving on the 2-approximation algorithms of Azar & Epstein; and (iii) the first constant-factor multicriteria approximation algorithms that handle the weighted completion-time and any given collection of integer L/sub p/ norms. Our algorithm yields a common generalization of rounding theorems due to Karp et al and Shmoys & Tardos; among other applications, this yields an improved approximation for scheduling with resource-dependent processing times studied by Grigoriev et al.

Details

FOCS Conference 2002 Conference Paper

Dependent Rounding in Bipartite Graphs

  • Rajiv Gandhi
  • Samir Khuller
  • Srinivasan Parthasarathy 0002
  • Aravind Srinivasan

We combine the pipage rounding technique of Ageev & Sviridenko with a recent rounding method developed by Srinivasan (2001), to develop a new randomized rounding approach for fractional vectors defined on the edge-sets of bipartite graphs. We show various ways of combining this technique with other ideas, leading to the following applications: richer random-graph models for graphs with a given degree-sequence; improved approximation algorithms for: (i) throughput-maximization in broadcast scheduling, (ii) delay-minimization in broadcast scheduling, and (iii) capacitated vertex cover; fair scheduling of jobs on unrelated parallel machines. A useful feature of our method is that it lets us prove certain (probabilistic) per-user fairness properties.

Details

FOCS Conference 2001 Conference Paper

Distributions on Level-Sets with Applications to Approximation Algorithms

  • Aravind Srinivasan

We consider a family of distributions on fixed-weight vectors in {0, 1}/sup t/; these distributions enjoy certain negative correlation properties and also satisfy pre-specified conditions on their marginal distributions. We show the existence of such families, and present a linear-time algorithm to sample from them. This yields improved approximation algorithms for the following problems: (a) low-congestion multi-path routing; (b) maximum coverage versions of set cover; (c) partial vertex cover problems for bounded-degree graphs; and (d) the Group Steiner Tree problem. For (a) and (b), the improvement is in the approximation ratio; for (c), we show how to speedup existing approximation algorithms while preserving the best-known approximation ratio; we also improve the approximation ratio for certain families of instances of unbounded degree. For (d), we derive an approximation algorithm whose approximation guarantee is at least as good as what is known; our algorithm is shown to have a better approximation guarantee for the worst known input families for existing algorithms.

Details

FOCS Conference 1998 Conference Paper

Improved Bounds and Algorithms for Hypergraph Two-Coloring

  • Jaikumar Radhakrishnan
  • Aravind Srinivasan

We show that for all large n, every n-uniform hypergraph with at most 0. 7/spl radic/(n/lnn)/spl times/2/sup n/ edges can be two-colored. We, in fact, present fast algorithms that output a proper two-coloring with high probability for such hypergraphs. We also derandomize and parallelize these algorithms, to derive NC/sup 1/ versions of these results. This makes progress on a problem of Erdos (1963), improving the previous-best bound of n/sup 1/3-0(1)//spl times/2/sup n/ due to Beck (1978). We further generalize this to a "local" version, improving on one of the first applications of the Lovasz Local Lemma.

Details

FOCS Conference 1995 Conference Paper

Contention Resolution with Bounded Delay

  • Mike Paterson
  • Aravind Srinivasan

When distributed processes contend for a shared resource, we need a good distributed contention resolution protocol, e. g. , for multiple-access channels (ALOHA, Ethernet), PRAM emulation, and optical routing. Under a stochastic model of request generation from n synchronous processes, Raghavan & Upfal (1995) have shown a protocol which is stable for a positive request rate; their main result is that for every resource request, its expected delay (time to get serviced) is O(log n). Assuming that the initial clock times of the processes are within a known bound of each other, we present a stable protocol, wherein the expected delay for each request is O(1). We derive this by showing an analogous result for can infinite number of processes, assuming that all processes agree on the time.

Details

FOCS Conference 1995 Conference Paper

Splitters and Near-Optimal Derandomization

  • Moni Naor
  • Leonard J. Schulman
  • Aravind Srinivasan

We present a fairly general method for finding deterministic constructions obeying what we call k-restrictions; this yields structures of size not much larger than the probabilistic bound. The structures constructed by our method include (n, k)-universal sets (a collection of binary vectors of length n such that for any subset of size k of the indices, all 2/sup k/ configurations appear) and families of perfect hash functions. The near-optimal constructions of these objects imply the very efficient derandomization of algorithms in learning, of fixed-subgraph finding algorithms, and of near optimal /spl Sigma/II/spl Sigma/ threshold formulae. In addition, they derandomize the reduction showing the hardness of approximation of set cover. They also yield deterministic constructions for a local-coloring protocol, and for exhaustive testing of circuits.

Details

FOCS Conference 1994 Conference Paper

Computing with Very Weak Random Sources

  • Aravind Srinivasan
  • David Zuckerman

For any fixed /spl epsiv/>0, we show how to simulate RP algorithms in time n/sup O(log n/) using the output of a /spl delta/-source with min-entropy R(/spl epsiv/). Such a weak random source is asked once for R(/spl epsiv/) bits; it outputs an R-bit string such that any string has probability at most 2/sup -R/(/spl epsiv//). If /spl epsiv/>1-1/(k+1), our BPP simulations take time n/sup O(log(k/ n)) (log/sup (k/) is the logarithm iterated k times). We also give a polynomial-time BPP simulation using Chor-Goldreich sources of min-entropy R/sup /spl Omega/(1/), which is optimal. We present applications to time-space tradeoffs, expander constructions, and the hardness of approximation. Also of interest is our randomness-efficient Leftover Hash Lemma, found independently by Goldreich and Wigderson. >

Details