46 citations · 101 across the 26 of their papers we have counts for
17 papers · 1 filter
Barely Monotone (min,+)-Convolution in Truly Subquadratic Time
MohammadTaghi Hajiaghayi, Danny Mittal, Saeed Seddighin
The (min,+)-convolution of two sequences A and B of length n is the sequence C with C[k] = min_{i+j=k} (A[i]+B[j]). For bounded inputs, whose entries are integers in {0,...,O(n)},…
Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond
Kiarash Banihashem, Jeff Giliberti, Samira Goudarzi +3
In this paper, we study the fundamental problems of maintaining the diameter and a -center clustering of a dynamic point set , where points may be insert…
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…
Pandora with Inaccurate Priors
Kiarash Banihashem, Xiang Chen, MohammadTaghi Hajiaghayi +4
We investigate the role of inaccurate priors for the classical Pandora's box problem. In the classical Pandora's box problem we are given a set of boxes each with a known cost and…
A Dynamic Algorithm for Weighted Submodular Cover Problem
Kiarash Banihashem, Samira Goudarzi, MohammadTaghi Hajiaghayi +2
We initiate the study of the submodular cover problem in dynamic setting where the elements of the ground set are inserted and deleted. In the classical submodular cover problem, w…
Prize-Collecting Steiner Tree: A 1.79 Approximation
Ali Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi +2
Prize-Collecting Steiner Tree (PCST) is a generalization of the Steiner Tree problem, a fundamental problem in computer science. In the classic Steiner Tree problem, we aim to conn…
Dynamic Non-monotone Submodular Maximization
Kiarash Banihashem, Leyla Biabani, Samira Goudarzi +3
Maximizing submodular functions has been increasingly used in many applications of machine learning, such as data summarization, recommendation systems, and feature selection. More…
2-Approximation for Prize-Collecting Steiner Forest
Ali Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi +2
Approximation algorithms for the prize-collecting Steiner forest problem (PCSF) have been a subject of research for over three decades, starting with the seminal works of Agrawal,…
Stochastic Matching with Few Queries: Approximation
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi
Suppose that we are given an arbitrary graph and know that each edge in is going to be realized independently with some probability . The goal in the stochastic m…
Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi +2
We present the first algorithm for maintaining a maximal independent set (MIS) of a fully dynamic graph---which undergoes both edge insertions and deletions---in polylogarithmic ti…
Exponentially Faster Massively Parallel Maximal Matching
Soheil Behnezhad, MohammadTaghi Hajiaghayi, David G. Harris
The study of approximate matching in the Massively Parallel Computations (MPC) model has recently seen a burst of breakthroughs. Despite this progress, however, we still have a far…
Applications of Uniform Sampling: Densest Subgraph and Beyond
Hossein Esfandiari, MohammadTaghi Hajiaghayi, David P. Woodruff
Recently [Bhattacharya et al., STOC 2015] provide the first non-trivial algorithm for the densest subgraph problem in the streaming model with additions and deletions to its edges,…
A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median
Mohammadtaghi Hajiaghayi, Wei Hu, Jian Li +2
In this paper, we consider the fault-tolerant -median problem and give the \emph{first} constant factor approximation algorithm for it. In the fault-tolerant generalization of c…
Minimizing Movement: Fixed-Parameter Tractability
Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx
We study an extensive class of movement minimization problems which arise from many practical scenarios but so far have little theoretical study. In general, these problems involve…
On the Integrality Gap of the Directed-Component Relaxation for Steiner Tree
Mohammad Taghi Hajiaghayi, Shi Li
In this note, we show that the integrality gap of the -Directed-Component- Relaxation(-DCR) LP for the Steiner tree problem, introduced by Byrka, Grandoni, Rothvob and Sanita…
Euclidean Prize-collecting Steiner Forest
MohammadHossein Bateni, MohammadTaghi Hajiaghayi
In this paper, we consider Steiner forest and its generalizations, prize-collecting Steiner forest and k-Steiner forest, when the vertices of the input graph are points in the Eucl…
Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Dániel Marx
We give the first polynomial-time approximation scheme (PTAS) for the Steiner forest problem on planar graphs and, more generally, on graphs of bounded genus. As a first step, we s…