Sublinear-Time and Semi-Streaming Algorithms for Path Cover and TSP

Sharareh Alipour, Ali Nowzari

We give improved sublinear-time and semi-streaming approximation algorithms for maximum path cover, $(1,2)$-TSP, and Max-TSP. For each fixed $\eps>0$, our distance-query algorithm…