  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.
