MMMorteza Monemizadeh
Morteza Monemizadeh
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Morteza Monemizadeh has a total of 10 co-authors. Here are the top co-authors by number of shared publications:
- Kiarash Banihashem
University of Maryland College Park MD USA
3 shared publications - MohammadTaghi Hajiaghayi
University of Maryland, College Park, USA
3 shared publications - Samira Goudarzi
Computer Science Department University of Maryland College Park MD USA
3 shared publications - Leyla Biabani
Department of Mathematics and Computer Science TU Eindhoven The Netherlands
2 shared publications - Peyman Jabbarzade
University of Maryland College Park MD USA
2 shared publications - Jeff Giliberti
Department of Computer Science University of Maryland 8125 Paint Branch Dr; College Park 20742 MD USA
1 shared publication
Latest Publications
- Open Access
Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond
In this paper, we study the fundamental problems of maintaining the diameter and a $k$-center clustering of a dynamic point set $P \subset \mathbb{R}^d$, where points may be inserted or deleted over time and the ambient dimension $d$ is not constant and may be high. Our focus is on designing algorithms that remain effective even in the presence of an adaptive adversary -- an adversary that, at any time $t$, knows the entire history of the algorithm's outputs as well as all the random bits used by the algorithm up to that point. We present a fully dynamic algorithm that maintains a $2$-approximate diameter with a worst-case update time of $\text{poly}(d, \log n)$, where $n$ is the length of the stream. Our result is achieved by identifying a robust representative of the dataset that requires infrequent updates, combined with a careful deamortization. To the best of our knowledge, this is the first efficient fully-dynamic algorithm for diameter in high dimensions that simultaneously achieves a 2-approximation guarantee and robustness against an adaptive adversary. We also give an improved dynamic $(4+ε)$-approximation algorithm for the $k$-center problem, also resilient to an adaptive adversary. Our clustering algorithm achieves an amortized update time of $k^{2.5} d \cdot \text{poly}(ε^{-1}, \log n)$, improving upon the amortized update time of $k^6 d \cdot \text{poly}(ε^{-1}, \log n)$ by Biabani et al. [NeurIPS'24].Open AccessDynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond
In this paper, we study the fundamental problems of maintaining the diameter and a $k$-center clustering of a dynamic point set $P \subset \mathbb{R}^d$, where points may be inserted or deleted over time and the ambient dimension $d$ is not constant and may be high. Our focus is on designing algorithms that remain effective even in the presence of an adaptive adversary -- an adversary that, at any time $t$, knows the entire history of the algorithm's outputs as well as all the random bits used by the algorithm up to that point. We present a fully dynamic algorithm that maintains a $2$-approximate diameter with a worst-case update time of $\text{poly}(d, \log n)$, where $n$ is the length of the stream. Our result is achieved by identifying a robust representative of the dataset that requires infrequent updates, combined with a careful deamortization. To the best of our knowledge, this is the first efficient fully-dynamic algorithm for diameter in high dimensions that simultaneously achieves a 2-approximation guarantee and robustness against an adaptive adversary. We also give an improved dynamic $(4+ε)$-approximation algorithm for the $k$-center problem, also resilient to an adaptive adversary. Our clustering algorithm achieves an amortized update time of $k^{2.5} d \cdot \text{poly}(ε^{-1}, \log n)$, improving upon the amortized update time of $k^6 d \cdot \text{poly}(ε^{-1}, \log n)$ by Biabani et al. [NeurIPS'24]. - Open Access
Dynamic Algorithms for Matroid Submodular Maximization
Submodular maximization under matroid and cardinality constraints are classical problems with a wide range of applications in machine learning, auction theory, and combinatorial optimization. In this paper, we consider these problems in the dynamic setting, where (1) we have oracle access to a monotone submodular function $f: 2^{V} \rightarrow \mathbb{R}^+$ and (2) we are given a sequence $\mathcal{S}$ of insertions and deletions of elements of an underlying ground set $V$. We develop the first fully dynamic $(4+ε)$-approximation algorithm for the submodular maximization problem under the matroid constraint using an expected worst-case $O(k\log(k)\log^3{(k/ε)})$ query complexity where $0 < ε\le 1$. This resolves an open problem of Chen and Peng (STOC'22) and Lattanzi et al. (NeurIPS'20). As a byproduct, for the submodular maximization under the cardinality constraint $k$, we propose a parameterized (by the cardinality constraint $k$) dynamic algorithm that maintains a $(2+ε)$-approximate solution of the sequence $\mathcal{S}$ at any time $t$ using an expected worst-case query complexity $O(kε^{-1}\log^2(k))$. This is the first dynamic algorithm for the problem that has a query complexity independent of the size of ground set $V$.Open AccessDynamic Algorithms for Matroid Submodular Maximization
Submodular maximization under matroid and cardinality constraints are classical problems with a wide range of applications in machine learning, auction theory, and combinatorial optimization. In this paper, we consider these problems in the dynamic setting, where (1) we have oracle access to a monotone submodular function $f: 2^{V} \rightarrow \mathbb{R}^+$ and (2) we are given a sequence $\mathcal{S}$ of insertions and deletions of elements of an underlying ground set $V$. We develop the first fully dynamic $(4+ε)$-approximation algorithm for the submodular maximization problem under the matroid constraint using an expected worst-case $O(k\log(k)\log^3{(k/ε)})$ query complexity where $0 < ε\le 1$. This resolves an open problem of Chen and Peng (STOC'22) and Lattanzi et al. (NeurIPS'20). As a byproduct, for the submodular maximization under the cardinality constraint $k$, we propose a parameterized (by the cardinality constraint $k$) dynamic algorithm that maintains a $(2+ε)$-approximate solution of the sequence $\mathcal{S}$ at any time $t$ using an expected worst-case query complexity $O(kε^{-1}\log^2(k))$. This is the first dynamic algorithm for the problem that has a query complexity independent of the size of ground set $V$. - Open Access
Dynamic Constrained Submodular Optimization with Polylogarithmic Update Time
Maximizing a monotone submodular function under cardinality constraint $k$ is a core problem in machine learning and database with many basic applications, including video and data summarization, recommendation systems, feature extraction, exemplar clustering, and coverage problems. We study this classic problem in the fully dynamic model where a stream of insertions and deletions of elements of an underlying ground set is given and the goal is to maintain an approximate solution using a fast update time. A recent paper at NeurIPS'20 by Lattanzi, Mitrovic, Norouzi{-}Fard, Tarnawski, Zadimoghaddam claims to obtain a dynamic algorithm for this problem with a $\frac{1}{2} -ε$ approximation ratio and a query complexity bounded by $\mathrm{poly}(\log(n),\log(k),ε^{-1})$. However, as we explain in this paper, the analysis has some important gaps. Having a dynamic algorithm for the problem with polylogarithmic update time is even more important in light of a recent result by Chen and Peng at STOC'22 who show a matching lower bound for the problem -- any randomized algorithm with a $\frac{1}{2}+ε$ approximation ratio must have an amortized query complexity that is polynomial in $n$. In this paper, we develop a simpler algorithm for the problem that maintains a $(\frac{1}{2}-ε)$-approximate solution for submodular maximization under cardinality constraint $k$ using a polylogarithmic amortized update time.Open AccessDynamic Constrained Submodular Optimization with Polylogarithmic Update Time
Maximizing a monotone submodular function under cardinality constraint $k$ is a core problem in machine learning and database with many basic applications, including video and data summarization, recommendation systems, feature extraction, exemplar clustering, and coverage problems. We study this classic problem in the fully dynamic model where a stream of insertions and deletions of elements of an underlying ground set is given and the goal is to maintain an approximate solution using a fast update time. A recent paper at NeurIPS'20 by Lattanzi, Mitrovic, Norouzi{-}Fard, Tarnawski, Zadimoghaddam claims to obtain a dynamic algorithm for this problem with a $\frac{1}{2} -ε$ approximation ratio and a query complexity bounded by $\mathrm{poly}(\log(n),\log(k),ε^{-1})$. However, as we explain in this paper, the analysis has some important gaps. Having a dynamic algorithm for the problem with polylogarithmic update time is even more important in light of a recent result by Chen and Peng at STOC'22 who show a matching lower bound for the problem -- any randomized algorithm with a $\frac{1}{2}+ε$ approximation ratio must have an amortized query complexity that is polynomial in $n$. In this paper, we develop a simpler algorithm for the problem that maintains a $(\frac{1}{2}-ε)$-approximate solution for submodular maximization under cardinality constraint $k$ using a polylogarithmic amortized update time. - Open Access
- 15 October 2022
- Published by Springer Nature in Algorithmica
- Vol. 85 (6) , 1652-1678
Clique-Based Separators for Geometric Intersection Graphs
Let F be a set of n objects in the plane and let $$\mathcal {G}^{\times }(F)$$ be its intersection graph. A balanced clique-based separator of $$\mathcal {G}^{\times }(F)$$ is a set $$\mathcal {\mathcal {S}}$$ consisting of cliques whose removal partitions $$\mathcal {G}^{\times }(F)$$ into components of size at most $$\delta n$$ , for some fixed constant $$\delta <1$$ . The weight of a clique-based separator is defined as $$\sum _{C\in \mathcal {\mathcal {S}}}\log (|C|+1)$$ . Recently De Berg et al. (SIAM J. Comput. 49: 1291-1331. 2020) proved that if S consists of convex fat objects, then $$\mathcal {G}^{\times }(F)$$ admits a balanced clique-based separator of weight $$O(\sqrt{n})$$ . We extend this result in several directions, obtaining the following results. (i) Map graphs admit a balanced clique-based separator of weight $$O(\sqrt{n})$$ , which is tight in the worst case. (ii) Intersection graphs of pseudo-disks admit a balanced clique-based separator of weight $$O(n^{2/3}\log n)$$ . If the pseudo-disks are polygonal and of total complexity O(n) then the weight of the separator improves to $$O(\sqrt{n}\log n)$$ . (iii) Intersection graphs of geodesic disks inside a simple polygon admit a balanced clique-based separator of weight $$O(n^{2/3}\log n)$$ . (iv) Visibility-restricted unit-disk graphs in a polygonal domain with r reflex vertices admit a balanced clique-based separator of weight $$O(\sqrt{n}+r\log (n/r))$$ , which is tight in the worst case. These results immediately imply sub-exponential algorithms for Maximum Independent Set (and, hence, Vertex Cover), for Feedback Vertex Set, and for q-Coloring for constant q in these graph classes.- 15 October 2022
- Published by Springer Nature in Algorithmica
- Vol. 85 (6) , 1652-1678
Open AccessClique-Based Separators for Geometric Intersection Graphs
Let F be a set of n objects in the plane and let $$\mathcal {G}^{\times }(F)$$ be its intersection graph. A balanced clique-based separator of $$\mathcal {G}^{\times }(F)$$ is a set $$\mathcal {\mathcal {S}}$$ consisting of cliques whose removal partitions $$\mathcal {G}^{\times }(F)$$ into components of size at most $$\delta n$$ , for some fixed constant $$\delta <1$$ . The weight of a clique-based separator is defined as $$\sum _{C\in \mathcal {\mathcal {S}}}\log (|C|+1)$$ . Recently De Berg et al. (SIAM J. Comput. 49: 1291-1331. 2020) proved that if S consists of convex fat objects, then $$\mathcal {G}^{\times }(F)$$ admits a balanced clique-based separator of weight $$O(\sqrt{n})$$ . We extend this result in several directions, obtaining the following results. (i) Map graphs admit a balanced clique-based separator of weight $$O(\sqrt{n})$$ , which is tight in the worst case. (ii) Intersection graphs of pseudo-disks admit a balanced clique-based separator of weight $$O(n^{2/3}\log n)$$ . If the pseudo-disks are polygonal and of total complexity O(n) then the weight of the separator improves to $$O(\sqrt{n}\log n)$$ . (iii) Intersection graphs of geodesic disks inside a simple polygon admit a balanced clique-based separator of weight $$O(n^{2/3}\log n)$$ . (iv) Visibility-restricted unit-disk graphs in a polygonal domain with r reflex vertices admit a balanced clique-based separator of weight $$O(\sqrt{n}+r\log (n/r))$$ , which is tight in the worst case. These results immediately imply sub-exponential algorithms for Maximum Independent Set (and, hence, Vertex Cover), for Feedback Vertex Set, and for q-Coloring for constant q in these graph classes.