83 citations · 133 across the 14 of their papers we have counts for
16 papers
A General Framework for Matching with Delays
Sara Ahmadian, Shuchi Chawla, Ravi Kumar +2
We present a simple deterministic -competitive algorithm for the online minimum-cost perfect matching with delays (MPMD) problem on arbitrary, unknown metric spaces, whe…
Multi-Level Aggregation via Dual Fitting: An -Competitive Algorithm
Sara Ahmadian, Shuchi Chawla, Ravi Kumar +2
We present a new online algorithm for the well-known Multi-Level Aggregation Problem (MLAP) with arbitrary delay functions, achieving a -competitive ratio, where is the dep…
DeMEtRIS: Counting (near)-Cliques by Crawling
Suman K. Bera, Jayesh Choudhari, Shahrzad Haddadan +1
We study the problem of approximately counting cliques and near cliques in a graph, where the access to the graph is only available through crawling its vertices; thus typically se…
Improved Approximation for Fair Correlation Clustering
Sara Ahmadian, Maryam Negahbani
Correlation clustering is a ubiquitous paradigm in unsupervised machine learning where addressing unfairness is a major challenge. Motivated by this, we study Fair Correlation Clus…
Maximizing Agreements for Ranking, Clustering and Hierarchical Clustering via MAX-CUT
Vaggos Chatziafratis, Mohammad Mahdian, Sara Ahmadian
In this paper, we study a number of well-known combinatorial optimization problems that fit in the following paradigm: the input is a collection of (potentially inconsistent) local…
The Wedge Picking Model: A dynamic graph model based on triadic closure
Sara Ahmadian, Shahrzad Haddadan
Social networks have become an inseparable part of human life and processing them in an efficient manner is a top priority in the study of networks. These networks are highly dynam…
Fair Hierarchical Clustering
Sara Ahmadian, Alessandro Epasto, Marina Knittel +6
As machine learning has become more prevalent, researchers have begun to recognize the necessity of ensuring machine learning systems are fair. Recently, there has been an interest…
Fair Correlation Clustering
Sara Ahmadian, Alessandro Epasto, Ravi Kumar +1
In this paper, we study correlation clustering under fairness constraints. Fair variants of -median and -center clustering have been studied recently, and approximation algor…
Fair Correlation Clustering
Saba Ahmadi, Sainyam Galhotra, Barna Saha +1
In this paper we study the problem of correlation clustering under fairness constraints. In the classic correlation clustering problem, we are given a complete graph where each edg…
Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection
Sara Ahmadian, Vaggos Chatziafratis, Alessandro Epasto +4
Hierarchical Clustering is an unsupervised data analysis method which has been widely used for decades. Despite its popularity, it had an underdeveloped analytical foundation and t…
Clustering without Over-Representation
Sara Ahmadian, Alessandro Epasto, Ravi Kumar +1
In this paper we consider clustering problems in which each point is endowed with a color. The goal is to cluster the points to minimize the classical clustering cost but with the…
Further Approximations for Demand Matching: Matroid Constraints and Minor-Closed Graphs
Sara Ahmadian, Zachary Friggstad
We pursue a study of the Generalized Demand Matching problem, a common generalization of the -Matching and Knapsack problems. Here, we are given a graph with vertex capacities,…
Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms
Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson +1
Clustering is a classic topic in optimization with -means being one of the most fundamental such problems. In the absence of any restrictions on the input, the best known algori…
Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers
Sara Ahmadian, Chaitanya Swamy
We consider clustering problems with {\em non-uniform lower bounds and outliers}, and obtain the {\em first approximation guarantees} for these problems. We have a set $\F$ of faci…
Local-Search based Approximation Algorithms for Mobile Facility Location Problems
Sara Ahmadian, Zachary Friggstad, Chaitanya Swamy
We consider the {\em mobile facility location} (\mfl) problem. We are given a set of facilities and clients located in a common metric space. The goal is to move each facility from…
Improved Approximation Guarantees for Lower-Bounded Facility Location
Sara Ahmadian, Chaitanya Swamy
We consider the {\em lower-bounded facility location} (\lbfl) problem (also sometimes called {\em load-balanced facility location}), which is a generalization of {\em uncapacitated…