We develop polynomial-size LP-relaxations for { \em orienteering} and the { \em regret-bounded vehicle routing problem} (\rvrp) and devise suitable LP-rounding algorithms that lead to various new insights and approximation results for these problems. In orienteering, the goal is to find a maximum-reward $r$-rooted path, possibly ending at a specified node, of length at most some given budget $B$. In \rvrp, the goal is to find the minimum number of $r$-rooted paths of { \em regret} at most a given bound $R$ that cover all nodes, where the regret of an $r$-$v$ path is its length $-$ $c_{ rv}$. For { \em rooted orienteering}, we introduce a natural bidirected LP-relaxation and obtain a simple $3$-approximation algorithm via LP-rounding. This is the { \em first LP-based} guarantee for this problem. We also show that { \em point-to-point} (\ptp) { \em orienteering} can be reduced to a regret-version of rooted orienteering at the expense of a factor-2 loss in approximation. For \rvrp, we propose two compact LPs that lead to significant improvements, in both approximation ratio and running time, over the approach in~\cite{ FriggstadS14}. One of these is a natural modification of the LP for rooted orienteering; the other is an unconventional formulation that is motivated by certain structural properties of an \rvrp-solution, which leads to a $15$-approximation algorithm for \rvrp.
Categories: cs.DS