10 papers
Online Steiner Forest with Recourse
Yaowei Long, Sepideh Mahabadi, Sherry Sarkar +1
In the online Steiner forest problem we are given a graph , and a sequence of terminal pairs which arrive in an online fashion. We are asked to maintain a low-cost s…
Improved Algorithms for Fair Matroid Submodular Maximization
Sepideh Mahabadi, Sherry Sarkar, Jakub Tarnawski
Submodular maximization subject to matroid constraints is a central problem with many applications in machine learning. As algorithms are increasingly used in decision-making over…
Sublinear Metric Steiner Forest via Maximal Independent Set
Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski +1
In this work we consider the Metric Steiner Forest problem in the sublinear time model. Given a set of points in a metric space where distances are provided by means of que…
Composable Coresets for Constrained Determinant Maximization and Beyond
Sepideh Mahabadi, Thuy-Duong Vuong
We study algorithms for construction of composable coresets for the task of Determinant Maximization under partition constraint. Given a point set that is p…
The Expiration Streaming Model: Diameter, -Center, Counting, Sampling, and Friends
Lotte Blank, Sergio Cabello, MohammadTaghi Hajiaghayi +5
An important thread in the study of data-stream algorithms focuses on settings where stream items are active only for a limited time. We introduce a new expiration model, where eac…
A 0.51-Approximation of Maximum Matching in Sublinear Time
Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski
We study the problem of estimating the size of a maximum matching in sublinear time. The problem has been studied extensively in the literature and various algorithms and lower bou…