We develop polynomial-size LP-relaxations for orienteering and the 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 specied node, of length at most some given budget B. In RVRP, the goal is to find the minimum number of r-rooted paths of regret at most a given bound R that cover all nodes, where the regret of an r-v path is its length - (distance of v from r).

For orienteering without a specified end-node, we introduce a natural bidirected LP-relaxation and obtain a simple 3-approximation algorithm via LP-rounding. This is the first LP-based guarantee for this problem. We also show that point-to-point orienteering (where the end-node is also specified) 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 signicant improvements, in both approximation ratio and running time, over the previous O(1)-factor approximation algorithm. One of these LPs is a rather unconventional formulation that leverages various structural properties of an RVRP-solution.

This is joint work with Zachary Friggstad.