2015 | OriginalPaper | Buchkapitel
Smoothed Analysis of the Squared Euclidean Maximum-Cut Problem
verfasst von : Michael Etscheid, Heiko Röglin
Erschienen in: Algorithms - ESA 2015
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
It is well-known that local search heuristics for the Maximum-Cut problem can take an exponential number of steps to find a local optimum, even though they usually stabilize quickly in experiments. To explain this discrepancy we have recently analyzed the simple local search algorithm FLIP in the framework of smoothed analysis, in which inputs are subject to a small amount of random noise. We have shown that in this framework the number of iterations is quasi-polynomial, i.e., it is polynomially bounded in
n
log
n
and
φ
, where
n
denotes the number of nodes and
φ
is a parameter of the perturbation.
In this paper we consider the special case in which the nodes are points in a
d
-dimensional space and the edge weights are given by the squared Euclidean distances between these points. We prove that in this case for any constant dimension
d
the smoothed number of iterations of FLIP is polynomially bounded in
n
and 1/
σ
, where
σ
denotes the standard deviation of the Gaussian noise. Squared Euclidean distances are often used in clustering problems and our result can also be seen as an upper bound on the smoothed number of iterations of local search for min-sum 2-clustering.