Source author record

Amir Nayyeri

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms Artificial Intelligence Discrete Mathematics math.AT math.NA Multiagent Systems Numerical Analysis Robotics

Catalog footprint

Research overview

11works

9topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

ETH-tight algorithms for finding surfaces in simplicial complexes of bounded treewidth

Given a simplicial complex with $n$ simplices, we consider the Connected Subsurface Recognition (c-SR) problem of finding a subcomplex that is homeomorphic to a given connected surface with a fixed boundary. We also study the related Sum-of-Genus Subsurface Recognition (SoG) problem, where we instead search for a surface whose boundary, number of connected components, and total genus are given. For both of these problems, we give parameterized algorithms with respect to the treewidth $k$ of the Hasse diagram that run in $2^{O(k \log k)}n^{O(1)}$ time. For the SoG problem, we also prove that our algorithm is optimal assuming the exponential-time hypothesis. In fact, we prove the stronger result that our algorithm is ETH-tight even without restriction on the total genus.

preprint2022arXiv

Finding minimum bounded and homologous chains in simplicial complexes with bounded-treewidth 1-skeleton

We consider two problems on simplicial complexes: the Optimal Bounded Chain Problem and the Optimal Homologous Chain Problem. The Optimal Bounded Chain Problem asks to find the minimum weight $d$ -chain in a simplicial complex $K$ bounded by a given $(d{-}1)$ -chain, if such a $d$ -chain exists. The Optimal Homologous Chain problem asks to find the minimum weight $(d{-}1)$ -chain in $K$ homologous to a given $(d{-}1)$ -chain. Both of these problems are NP-hard and hard to approximate within any constant factor assuming the Unique Games Conjecture. We prove that these problems are fixed-parameter tractable with respect to the treewidth of the 1-skeleton of $K$ .

preprint2022arXiv

Hodge Decomposition and General Laplacian Solvers for Embedded Simplicial Complexes

We describe a nearly-linear time algorithm to solve the linear system $L_1x = b$ parameterized by the first Betti number of the complex, where $L_1$ is the 1-Laplacian of a simplicial complex $K$ that is a subcomplex of a collapsible complex $X$ linearly embedded in $\mathbb{R}^{3}$ . Our algorithm generalizes the work of Black et al.~[SODA2022] that solved the same problem but required that $K$ have trivial first homology. Our algorithm works for complexes $K$ with arbitrary first homology with running time that is nearly-linear with respect to the size of the complex and polynomial with respect to the first Betti number. The key to our solver is a new algorithm for computing the Hodge decomposition of 1-chains of $K$ in nearly-linear time. Additionally, our algorithm implies a nearly quadratic solver and nearly quadratic Hodge decomposition for the 1-Laplacian of any simplicial complex $K$ embedded in $\mathbb{R}^{3}$ , as $K$ can always be expanded to a collapsible embedded complex of quadratic complexity.

preprint2022arXiv

On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem

We consider the following surveillance problem: Given a set $P$ of $n$ sites in a metric space and a set of $k$ robots with the same maximum speed, compute a patrol schedule of minimum latency for the robots. Here a patrol schedule specifies for each robot an infinite sequence of sites to visit (in the given order) and the latency $L$ of a schedule is the maximum latency of any site, where the latency of a site $s$ is the supremum of the lengths of the time intervals between consecutive visits to $s$ . When $k=1$ the problem is equivalent to the travelling salesman problem (TSP) and thus it is NP-hard. We have two main results. We consider cyclic solutions in which the set of sites must be partitioned into $\ell$ groups, for some~ $\ell \leq k$ , and each group is assigned a subset of the robots that move along the travelling salesman tour of the group at equal distance from each other. Our first main result is that approximating the optimal latency of the class of cyclic solutions can be reduced to approximating the optimal travelling salesman tour on some input, with only a $1+\varepsilon$ factor loss in the approximation factor and an $O\left(\left( k/\varepsilon \right)^k\right)$ factor loss in the runtime, for any $\varepsilon >0$ . Our second main result shows that an optimal cyclic solution is a $2(1-1/k)$ -approximation of the overall optimal solution. Note that for $k=2$ this implies that an optimal cyclic solution is optimal overall. The results have a number of consequences. For the Euclidean version of the problem, for instance, combining our results with known results on Euclidean TSP, yields a PTAS for approximating an optimal cyclic solution, and it yields a $(2(1-1/k)+\varepsilon)$ -approximation of the optimal unrestricted solution. If the conjecture mentioned above is true, then our algorithm is actually a PTAS for the general problem in the Euclidean setting.

preprint2020arXiv

Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency

We consider the problem of finding patrol schedules for $k$ robots to visit a given set of $n$ sites in a metric space. Each robot has the same maximum speed and the goal is to minimize the weighted maximum latency of any site, where the latency of a site is defined as the maximum time duration between consecutive visits of that site. The problem is NP-hard, as it has the traveling salesman problem as a special case (when $k=1$ and all sites have the same weight). We present a polynomial-time algorithm with an approximation factor of $O(k^2 \log \frac{w_{\max}}{w_{\min}})$ to the optimal solution, where $w_{\max}$ and $w_{\min}$ are the maximum and minimum weight of the sites respectively. Further, we consider the special case where the sites are in 1D. When all sites have the same weight, we present a polynomial-time algorithm to solve the problem exactly. If the sites may have different weights, we present a $12$ -approximate solution, which runs in polynomial time when the number of robots, $k$ , is a constant.

preprint2020arXiv

Low-stretch spanning trees of graphs with bounded width

We study the problem of low-stretch spanning trees in graphs of bounded width: bandwidth, cutwidth, and treewidth. We show that any simple connected graph $G$ with a linear arrangement of bandwidth $b$ can be embedded into a distribution $\mathcal T$ of spanning trees such that the expected stretch of each edge of $G$ is $O(b^2)$ . Our proof implies a linear time algorithm for sampling from $\mathcal T$ . Therefore, we have a linear time algorithm that finds a spanning tree of $G$ with average stretch $O(b^2)$ with high probability. We also describe a deterministic linear-time algorithm for computing a spanning tree of $G$ with average stretch $O(b^3)$ . For graphs of cutwidth $c$ , we construct a spanning tree with stretch $O(c^2)$ in linear time. Finally, when $G$ has treewidth $k$ we provide a dynamic programming algorithm computing a minimum stretch spanning tree of $G$ that runs in polynomial time with respect to the number of vertices of $G$ .

preprint2020arXiv

Minimum bounded chains and minimum homologous chains in embedded simplicial complexes

We study two optimization problems on simplicial complexes with homology over $\mathbb{Z}_2$ , the minimum bounded chain problem: given a $d$ -dimensional complex $\mathcal{K}$ embedded in $\mathbb{R}^{d+1}$ and a null-homologous $(d-1)$ -cycle $C$ in $\mathcal{K}$ , find the minimum $d$ -chain with boundary $C$ , and the minimum homologous chain problem: given a $(d+1)$ -manifold $\mathcal{M}$ and a $d$ -chain $D$ in $\mathcal{M}$ , find the minimum $d$ -chain homologous to $D$ . We show strong hardness results for both problems even for small values of $d$ ; $d = 2$ for the former problem, and $d=1$ for the latter problem. We show that both problems are APX-hard, and hard to approximate within any constant factor assuming the unique games conjecture. On the positive side, we show that both problems are fixed parameter tractable with respect to the size of the optimal solution. Moreover, we provide an $O(\sqrt{\log β_d})$ -approximation algorithm for the minimum bounded chain problem where $β_d$ is the $d$ th Betti number of $\mathcal{K}$ . Finally, we provide an $O(\sqrt{\log n_{d+1}})$ -approximation algorithm for the minimum homologous chain problem where $n_{d+1}$ is the number of $d$ -simplices in $\mathcal{M}$ .

preprint2016arXiv

Minimum cycle and homology bases of surface embedded graphs

We study the problems of finding a minimum cycle basis (a minimum weight set of cycles that form a basis for the cycle space) and a minimum homology basis (a minimum weight set of cycles that generates the $1$ -dimensional ( $\mathbb{Z}_2$ )-homology classes) of an undirected graph embedded on a surface. The problems are closely related, because the minimum cycle basis of a graph contains its minimum homology basis, and the minimum homology basis of the $1$ -skeleton of any graph is exactly its minimum cycle basis. For the minimum cycle basis problem, we give a deterministic $O(n^ω+2^{2g}n^2+m)$ -time algorithm for graphs embedded on an orientable surface of genus $g$ . The best known existing algorithms for surface embedded graphs are those for general graphs: an $O(m^ω)$ time Monte Carlo algorithm and a deterministic $O(nm^2/\log n + n^2 m)$ time algorithm. For the minimum homology basis problem, we give a deterministic $O((g+b)^3 n \log n + m)$ -time algorithm for graphs embedded on an orientable or non-orientable surface of genus $g$ with $b$ boundary components, assuming shortest paths are unique, improving on existing algorithms for many values of $g$ and $n$ . The assumption of unique shortest paths can be avoided with high probability using randomization or deterministically by increasing the running time of the homology basis algorithm by a factor of $O(\log n)$ .

preprint2015arXiv

Approximating Nearest Neighbor Distances

Several researchers proposed using non-Euclidean metrics on point sets in Euclidean space for clustering noisy data. Almost always, a distance function is desired that recognizes the closeness of the points in the same cluster, even if the Euclidean cluster diameter is large. Therefore, it is preferred to assign smaller costs to the paths that stay close to the input points. In this paper, we consider the most natural metric with this property, which we call the nearest neighbor metric. Given a point set P and a path $γ$ , our metric charges each point of $γ$ with its distance to P. The total charge along $γ$ determines its nearest neighbor length, which is formally defined as the integral of the distance to the input points along the curve. We describe a $(3+\varepsilon)$ -approximation algorithm and a $(1+\varepsilon)$ -approximation algorithm to compute the nearest neighbor metric. Both approximation algorithms work in near-linear time. The former uses shortest paths on a sparse graph using only the input points. The latter uses a sparse sample of the ambient space, to find good approximate geodesic paths.

preprint2015arXiv

How to Walk Your Dog in the Mountains with No Magic Leash

We describe a $O(\log n )$ -approximation algorithm for computing the homotopic \Frechet distance between two polygonal curves that lie on the boundary of a triangulated topological disk. Prior to this work, algorithms were known only for curves on the Euclidean plane with polygonal obstacles. A key technical ingredient in our analysis is a $O(\log n)$ -approximation algorithm for computing the minimum height of a homotopy between two curves. No algorithms were previously known for approximating this parameter. Surprisingly, it is not even known if computing either the homotopic \Frechet distance, or the minimum height of a homotopy, is in NP.

preprint2015arXiv

Towards single face shortest vertex-disjoint paths in undirected planar graphs

Given $k$ pairs of terminals $\{(s_{1}, t_{1}), \ldots, (s_{k}, t_{k})\}$ in a graph $G$ , the min-sum $k$ vertex-disjoint paths problem is to find a collection $\{Q_{1}, Q_{2}, \ldots, Q_{k}\}$ of vertex-disjoint paths with minimum total length, where $Q_{i}$ is an $s_i$ -to- $t_i$ path between $s_i$ and $t_i$ . We consider the problem in planar graphs, where little is known about computational tractability, even in restricted cases. Kobayashi and Sommer propose a polynomial-time algorithm for $k \le 3$ in undirected planar graphs assuming all terminals are adjacent to at most two faces. Colin de Verdiere and Schrijver give a polynomial-time algorithm when all the sources are on the boundary of one face and all the sinks are on the boundary of another face and ask about the existence of a polynomial-time algorithm provided all terminals are on a common face. We make progress toward Colin de Verdiere and Schrijver's open question by giving an $O(kn^5)$ time algorithm for undirected planar graphs when $\{(s_{1}, t_{1}), \ldots, (s_{k}, t_{k})\}$ are in counter-clockwise order on a common face.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Amir Nayyeri

Research overview

Is this your work?

11 publications

ETH-tight algorithms for finding surfaces in simplicial complexes of bounded treewidth

Finding minimum bounded and homologous chains in simplicial complexes with bounded-treewidth 1-skeleton

Hodge Decomposition and General Laplacian Solvers for Embedded Simplicial Complexes

On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem

Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency

Low-stretch spanning trees of graphs with bounded width

Minimum bounded chains and minimum homologous chains in embedded simplicial complexes

Minimum cycle and homology bases of surface embedded graphs

Approximating Nearest Neighbor Distances

How to Walk Your Dog in the Mountains with No Magic Leash

Towards single face shortest vertex-disjoint paths in undirected planar graphs

See the researcher in context

Building this map preview