Shorter tours and longer detours: Uniform covers and a bit beyond

Arash Haddadan, Alantha Newman, R. Ravi

Motivated by the well known four-thirds conjecture for the traveling salesman problem (TSP), we study the problem of {\em uniform covers}. A graph $G=(V,E)$ has an $\alpha$-uniform cove…