Introduction
NP-hard geometric optimization problems arise in many
disciplines. Perhaps the most famous one is the traveling salesman
problem (TSP): given n nodes in R^2 (more generally, in R^d), find the
minimum length path that visits each node exactly once. If distance is
computed using the Euclidean norm (distance between nodes (x_1,y_1) and
(x_2,y_2) is ((x_1-x_2)^2+(y_1-y_2)^2)^1/2) then the problem is called
Euclidean TSP. More generally the distance could be defined using
other norms, such as l_p norms for any p > 1. All these are subcases of
the more general notion of a geometric norm or Minkowski norm. We will
refer to the version of the problem with a general geometric norm as
geometric TSP.[1]
Some other NP-hard geometric optimization problems are Minimum
Steiner Tree (“Given n points, find the smallest network connecting
them,”), k- TSP(“Given n points and a number k, find the
shortest salesman tour that visits k points”), k-MST (“Given n
points and a number k, find the shortest tree that contains k
points”), vehicle routing, degree restricted minimum spanning tree,
etc. Thus if P \not= NP, as is widely conjectured, we cannot design
polynomial time algorithms to solve these problems optimally. However,
we might be able to design approximation algorithms: algorithms that
compute near-optimal solutions in polynomial time for every problem
instance. For \alpha \geq 1 we say that an algorithm approximates the
problem within a factor \alpha if it computes, for every instance I, a
solution of cost at most \alpha.OPT(I), where OPT(I) is the cost of
the optimum solution for I. (The preceding definition is for
minimization problems; for maximization problems \alpha \leq 1.)
Sometimes we use the shortened name “a-approximation algorithm.”
[1]
In this project, we aim to formalize the following problem in terms
of geometric TSP problem and hopefully we aim to find a solution to
the modified TSP problem.
Robotic Routers Problem (Volkan Isler and Onur Tekdas)
Mobile robots equipped with wireless networking capabilities can
provide network connectivity to mobile users. In this work, we present
motion planning algorithms for one or more robots to maintain the
connectivity of a single user (target) to a base-station. We already
found a dynamic programming algorithm for the target model where the
target's trajectory is known in advance. However, the running time of
this algorithm is exponential with the number of robotic routers.[Details]
Our goal in this project to formalize the robotic routers problem
in terms of TSP problem and find an approximation algorithm where the
running time is not exponentially depend on the number of robotic
routers.
Research Papers
