Compact, Provably-good LPs for Orienteering and Regret-bounded Vehicle Routing
summary
Presents compact polynomial-size LPs for rooted orienteering and regret-bounded vehicle routing, and an LP rounding that yields a 3-approximation LP rounding for rooted orienteering by expressing a directed preflow as a convex combination of rooted trees, converting each tree to a root–W path and splitting paths to meet regret bounds. Shows a reduction to point-to-point losing factor 2 (hence factor 6 overall) and an unorthodox compact LP giving a 15-approximation for regret-bounded VRP, uses arborescence packing, and leaves integrality gap tightening (likely 2) open.
AI-written summary · about