- 25 views
- 22 downloads
Approximation Scheme for Vehicle Routing Problems
-
- Author / Creator
- Ren, Zhong
-
In this thesis we consider the point to point orienteering and deadline traveling salesman problems on graphs with bounded treewidth and graphs with consant doubling dimension and present approximation schemes for them.
These are extensions of the classic Traveling Salesman Problem (TSP). Suppose we are given a (weighted) graph $G=(V,E)$. In point to point orienteering we are given a length budget $B$, start and end nodes $s,t \in V$ and the goal is to find a path of length at most $B$ starting at $s$ and ending at $t$ that visits as many vertices as possible. In deadline TSP we are given a start node $s\in V$ and $D(v) \geq 0$ (called deadline) for all $v\in V$ and the goal is to find a path starting at $s$ that visits as many vertices as possible before their deadline (where the visit time of a node is the distance travelled from $s$ to that node). On general metrics, the best approximation for point to point orienteering is $(2+\epsilon)$-approximation \cite{chekuri2012improved} and $O(\log n)$-approximation for deadline TSP \cite{bansal2004approximation}. On Euclidean space, \cite{chen2008euclidean} shows a polynomial time approximation scheme (PTAS) for rooted oritenteering. For graphs with bounded treewidth $\omega$ we show point to point orienteering can be solved exactly in polynomial time and a quasi-polynomial time approximation scheme (QPTAS) for deadline TSP when the distances are quasi-poly bounded and integers. For graphs with constant doubling dimension, we show QPTAS for point to point orienteering when the distances are quasi-poly bounded and a QPTAS for deadilne TSP when the distances are quasi-poly bounded and integers. -
- Subjects / Keywords
-
- Graduation date
- Fall 2024
-
- Type of Item
- Thesis
-
- Degree
- Master of Science
-
- License
- This thesis is made available by the University of Alberta Library with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.