Abstract: Two papers from SoCG 2009, by Mustafa and Ray and by Chan and
Har-Peled, prove (independently) that a simple local search strategy yields
a PTAS, provided that some properties hold. The algorithm used in both papers
is essentially the same: Given a parameter k, start with any feasible solution
and iteratively apply local improvement steps of the following kind:
If any k elements of the current solution can be replaced by k-1 elements s.t.
the resulting is still a feasible solution, then perform the swap, otherwise
stop.
This technique is quite general and has already found several applications.
The proofs are based on existence of bipartite graphs corresponding to
the input scene, where the obtained solution is proved to be
an "\epsilon-expand" of an optimal solution.
I plan to review these papers and a third one (by Gibson, Kanade, Krohn and Varadarajan) that applies this idea.