Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAsymptotic constant-factor approximation algorithm for the Traveling Salesperson Problem for Dubins vehicle
162
0
0.0
(
0
)
Added by
Ketan Savla
Publication date
2006
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This article proposes the first known algorithm that achieves a constant-factor approximation of the minimum length tour for a Dubins vehicle through $n$ points on the plane. By Dubins vehicle, we mean a vehicle constrained to move at constant speed along paths with bounded curvature without reversing direction. For this version of the classic Traveling Salesperson Problem, our algorithm closes the gap between previously established lower and upper bounds; the achievable performance is of order $n^{2/3}$.
rate research
Read More
In this paper, we study the problem of coverage planning by a mobile robot with a limited energy budget. The objective of the robot is to cover every point in the environment while minimizing the traveled path length. The environment is initially unknown to the robot. Therefore, it needs to avoid the obstacles in the environment on-the-fly during the exploration. As the robot has a specific energy budget, it might not be able to cover the complete environment in one traversal. Instead, it will need to visit a static charging station periodically in order to recharge its energy. To solve the stated problem, we propose a budgeted depth-first search (DFS)-based exploration strategy that helps the robot to cover any unknown planar environment while bounding the maximum path length to a constant-factor of the shortest-possible path length. Our $O(1)$-approximation guarantee advances the state-of-the-art of log-approximation for this problem. Simulation results show that our proposed algorithm outperforms the current state-of-the-art algorithm both in terms of the traveled path length and run time in all the tested environments with concave and convex obstacles.
Dubins tours represent a solution of the Dubins Traveling Salesman Problem (DTSP) that is a variant of the optimization routing problem to determine a curvature-constrained shortest path to visit a set of locations such that the path is feasible for Dubins vehicle, which moves only forward and has a limited turning radius. The DTSP combines the NP-hard combinatorial optimization to determine the optimal sequence of visits to the locations, as in the regular TSP, with the continuous optimization of the heading angles at the locations, where the optimal heading values depend on the sequence of visits and vice versa. We address the computationally challenging DTSP by fast evaluation of the sequence of visits by the proposed Windowing Surrogate Model (WiSM) which estimates the length of the optimal Dubins path connecting a sequence of locations in a Dubins tour. The estimation is sped up by a regression model trained using close to optimum solutions of small Dubins tours that are generalized for large-scale instances of the addressed DTSP utilizing the sliding window technique and a cache for already computed results. The reported results support that the proposed WiSM enables a fast convergence of a relatively simple evolutionary algorithm to high-quality solutions of the DTSP. We show that with an increasing number of locations, our algorithm scales significantly better than other state-of-the-art DTSP solvers.
The problem of vertex guarding a simple polygon was first studied by Subir K. Ghosh (1987), who presented a polynomial-time $O(log n)$-approximation algorithm for placing as few guards as possible at vertices of a simple $n$-gon $P$, such that every point in $P$ is visible to at least one of the guards. Ghosh also conjectured that this problem admits a polynomial-time algorithm with constant approximation ratio. Due to the centrality of guarding problems in the field of computational geometry, much effort has been invested throughout the years in trying to resolve this conjecture. Despite some progress (surveyed below), the conjecture remains unresolved to date. In this paper, we confirm the conjecture for the important case of weakly visible polygons, by presenting a $(2+varepsilon)$-approximation algorithm for guarding such a polygon using vertex guards. A simple polygon $P$ is weakly visible if it has an edge $e$, such that every point in $P$ is visible from some point on $e$. We also present a $(2+varepsilon)$-approximation algorithm for guarding a weakly visible polygon $P$, where guards may be placed anywhere on $P$s boundary (except in the interior of the edge $e$). Finally, we present a $3c$-approximation algorithm for vertex guarding a polygon $P$ that is weakly visible from a chord, given a subset $G$ of $P$s vertices that guards $P$s boundary whose size is bounded by $c$ times the size of a minimum such subset. Our algorithms are based on an in-depth analysis of the geometric properties of the regions that remain unguarded after placing guards at the vertices to guard the polygons boundary. It is plausible that our results will enable Bhattacharya et al. to complete their grand attempt to prove the original conjecture, as their approach is based on partitioning the underlying simple polygon into a hierarchy of weakly visible polygons.
One of the most fundamental results in combinatorial optimization is the polynomial-time 3/2-approximation algorithm for the metric traveling salesman problem. It was presented by Christofides in 1976 and is well known as the Christofides algorithm. Recently, some authors started calling it Christofides-Serdyukov algorithm, pointing out that it was published independently in the USSR in 1978. We provide some historic background on Serdyukovs findings and a translation of his article from Russian into English.
We present the first nontrivial approximation algorithm for the bottleneck asymmetric traveling salesman problem. Given an asymmetric metric cost between n vertices, the problem is to find a Hamiltonian cycle that minimizes its bottleneck (or maximum-length edge) cost. We achieve an O(log n / log log n) approximation performance guarantee by giving a novel algorithmic technique to shortcut Eulerian circuits while bounding the lengths of the shortcuts needed. This allows us to build on a related result of Asadpour, Goemans, Mk{a}dry, Oveis Gharan, and Saberi to obtain this guarantee. Furthermore, we show how our technique yields stronger approximation bounds in some cases, such as the bounded orientable genus case studied by Oveis Gharan and Saberi. We also explore the possibility of further improvement upon our main result through a comparison to the symmetric counterpart of the problem.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
