on October 17, 2019 at 2:00 pm
The effectiveness of Local Search
We present polynomial-time approximation schemes based on local search for facility location, k-median, and k-means in planar graphs or in Euclidean spaces of bounded dimension, where the local neighborhood of a solution consists of modifying the locations of a few centers. This can be viewed as an explanation for the effectiveness of local search heuristics in practice. This is based on joint work with Vincent Cohen-Addad and Philip Klein.
More...Amphi Ircica, Villeneuve d'Ascq
français
English