Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, June 19, 2007, 12:15 pm

Duration: This information is not available in the database

Location: CAB G51

Speaker: Reto Spöhel

Euclidean Vehicle Routing with Allocation

The (Euclidean) Vehicle Routing Allocation Problem (VRAP) is a generalization of Euclidean TSP. We do not require that all points lie on the salesman tour. However, points that do not lie on the tour are allocated, i.e., they are directly connected to the nearest tour point, paying a higher (per-unit) cost.

More formally, the input is a set of points $P\subset \R^d$ and functions $\alpha : P \to [0,\infty)$ and $\beta : P \to [1,\infty)$. We wish to compute a subset $T \subseteq P$ and a salesman tour $\pi$ through $T$ such that the total length of the tour plus the total allocation cost is minimum. The allocation cost for a single point $p \in P \setminus T$ is $\alpha(p) + \beta(p) \dist{p}{q}$, where $q \in T$ is the nearest point on the tour.

We give a PTAS with complexity $O(n \log^{d+3} n)$ for this problem. Moreover, we propose a $O(n \polylog{n})$-time PTAS for the Steiner variant of this problem. This dramatically improves a recent result of Armon et al. (ESA 2006).

Joint work with Jan Remy and Andreas Weissl.

Information for students and suggested topics for student talks