How to Keep an Eye on a Few Small Things
Bengt J. Nilsson, Paweł Żyliński · Malmö University Publications (Malmö University) · 2014
We present a (k +h)-FPT algorithm for computing a shortest tour that sees k specified points in a polygon with h holes. We also present a k-FPT approximation algorithm for this problem having approximation factor √2. In addition, we prove that the general problem cannot be polynomially approximated better than by a factor of (log n), unless P=NP, where n is the total number of edges of the polygon.