17 research outputs found
Improved Smoothed Analysis of 2-Opt for the Euclidean TSP
Full text linkThe 2-opt heuristic is a simple local search heuristic for the Travelling Salesperson Problem (TSP). Although it usually performs well in practice, its worst-case running time is poor. Attempts to reconcile this difference have used smoothed analysis, in which adversarial instances are perturbed probabilistically. We are interested in the classical model of smoothed analysis for the Euclidean TSP, in which the perturbations are Gaussian. This model was previously used by Manthey \& Veenstra, who obtained smoothed complexity bounds polynomial in , the dimension , and the perturbation strength . However, their analysis only works for . The only previous analysis for was performed by Englert, R\"oglin \& V\"ocking, who used a different perturbation model which can be translated to Gaussian perturbations. Their model yields bounds polynomial in and , and super-exponential in . As no direct analysis existed for Gaussian perturbations that yields polynomial bounds for all , we perform this missing analysis. Along the way, we improve all existing smoothed complexity bounds for Euclidean 2-opt
Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering
Full text linkWe analyze the running time of the Hartigan-Wong method, an old algorithm for the k-means clustering problem. First, we construct an instance on the line on which the method can take steps to converge, demonstrating that the Hartigan-Wong method has exponential worst-case running time even when k-means is easy to solve. As this is in contrast to the empirical performance of the algorithm, we also analyze the running time in the framework of smoothed analysis. In particular, given an instance of n points in d dimensions, we prove that the expected number of iterations needed for the Hartigan-Wong method to terminate is bounded by k^{12kd} \cdot \poly(n, k, d, 1/\sigma) when the points in the instance are perturbed by independent d-dimensional Gaussian random variables of mean 0 and standard deviation
Complexity of Local Search for Euclidean Clustering Problems
Full text linkWe show that the simplest local search heuristics for two natural Euclidean clustering problems are PLS-hard. First, we show that the Hartigan-Wong method, which is essentially the Flip heuristic, for k-Means clustering is PLS-hard, even when k = 2. Second, we show the same result for the Flip heuristic for Max Cut, even when the edge weights are given by the (squared) Euclidean distances between the points in some set ⊆ R^d; a problem which is equivalent to Min Sum 2-Clustering
Rigorous analysis of local search heuristics
Full text linkLocal search heuristics are standard methods in the optimizer's toolbox. These algorithms take as an input a candidate solution to an optimization problem and iteratively compute better solutions. Heuristics typically provide close-to-optimal solutions in much less running time than exact or approximation algorithms. Despite their practical usefulness, local search heuristics often have poor performance in the worst case. For many problems we know of instances where commonly used heuristics take prohibitively long to return a solution, or where they may return solutions that are far from optimal. This considerable gap between theory and practice is not satisfactory, as we would like to have some theoretical justification for using local search heuristics in practice. This dissertation broadly aims to enhance our understanding of local search heuristics. We analyze several heuristics using rigorous mathematical tools. We focus on three computational problems: the Travelling Salesperson Problem (TSP), k-Means clustering, and Max Cut. We consider these heuristics from the perspective of worst-case and beyond-worst-case analysis.For the TSP, we perform a smoothed analysis of the well-known 2-opt heuristic, improving and simplifying previous results for the Euclidean TSP. We then consider two polynomial-time variants of 2-opt, showing that one has poor approximation performance while the other performs similary to 2-opt. We moreover analyze the complexity of counting 2-optimal tours, and estimate the number of such tours in random instances. For k-Means clustering, we rigorously analyze the Hartigan-Wong method. This heuristic performs well in practice, but little was previously known about it theoretically. We show that even in one-dimensional instances, where k-Means can be solved optimally in polynomial time, the Hartigan-Wong method can take exponential time to find locally optimal clusterings. We also show that the heuristic leads to a PLS-complete local search problem. To augment these results we also perform the first smoothed analysis of the Hartigan-Wong method.Finally, we analyze the Flip heuristic for Max Cut, and show that also this simple heuristic yields a PLS-complete local search problem even in Euclidean instances
Improved Smoothed Analysis of 2-Opt for the Euclidean TSP
Full text linkThe 2-opt heuristic is a simple local search heuristic for the Travelling
Salesperson Problem (TSP). Although it usually performs well in practice, its
worst-case running time is poor. Attempts to reconcile this difference have
used smoothed analysis, in which adversarial instances are perturbed
probabilistically. We are interested in the classical model of smoothed
analysis for the Euclidean TSP, in which the perturbations are Gaussian. This
model was previously used by Manthey \& Veenstra, who obtained smoothed
complexity bounds polynomial in , the dimension , and the perturbation
strength . However, their analysis only works for . The
only previous analysis for was performed by Englert, R\"oglin \&
V\"ocking, who used a different perturbation model which can be translated to
Gaussian perturbations. Their model yields bounds polynomial in and
, and super-exponential in . As no direct analysis existed for
Gaussian perturbations that yields polynomial bounds for all , we perform
this missing analysis. Along the way, we improve all existing smoothed
complexity bounds for Euclidean 2-opt.Comment: 31 pages, 3 figures. Accepted for presentation at ISAAC 202
Approximation Ineffectiveness of a Tour-Untangling Heuristic
Full text linkWe analyze a tour-uncrossing heuristic for the Travelling Salesperson
Problem, showing that its worst-case approximation ratio is and its
average-case approximation ratio is in expectation. We
furthermore evaluate the approximation performance of this heuristic
numerically on average-case instances, and find that it performs far better
than the average-case lower bound suggests. This indicates a shortcoming in the
approach we use for our analysis, which is a rather common approach in the
analysis of local search heuristics.Comment: Accepted for presentation at WAOA 202
Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering
Full text linkWe analyze the running time of the Hartigan-Wong method, an old algorithm for
the -means clustering problem. First, we construct an instance on the line
on which the method can take steps to converge, demonstrating
that the Hartigan-Wong method has exponential worst-case running time even when
-means is easy to solve. As this is in contrast to the empirical performance
of the algorithm, we also analyze the running time in the framework of smoothed
analysis. In particular, given an instance of points in dimensions, we
prove that the expected number of iterations needed for the Hartigan-Wong
method to terminate is bounded by when
the points in the instance are perturbed by independent -dimensional
Gaussian random variables of mean and standard deviation .Comment: Accepted to STACS'24. 19 pages, 2 figure
Energy Derivatives in Real-Space Diffusion Monte Carlo
Full text linkWe present unbiased, finite-variance estimators of energy derivatives for real-space diffusion Monte Carlo calculations within the fixed-node approximation. The derivative dλE is fully consistent with the dependence E(λ) of the energy computed with the same time step. We address the issue of the divergent variance of derivatives related to variations of the nodes of the wave function both by using a regularization for wave function parameter gradients recently proposed in variational Monte Carlo and by introducing a regularization based on a coordinate transformation. The essence of the divergent variance problem is distilled into a particle-in-a-box toy model, where we demonstrate the algorithm
Counting Locally Optimal Tours in the TSP
Full text linkWe show that the problem of counting the number of 2-optimal tours in instances of the Travelling Salesperson Problem (TSP) on complete graphs is #P-complete. In addition, we show that the expected number of 2-optimal tours in random instances of the TSP on complete graphs is . Based on numerical experiments, we conjecture that the true bound is at most , which is approximately the square root of the total number of tours
Approximation Ineffectiveness of a Tour-Untangling Heuristic
Full text linkWe analyze a tour-uncrossing heuristic for the Travelling Salesperson Problem, showing that its worst-case approximation ratio is and its average-case approximation ratio is in expectation. We furthermore evaluate the approximation performance of this heuristic numerically on average-case instances, and find that it performs far better than the average-case lower bound suggests. This indicates a shortcoming in the approach we use for our analysis, which is a rather common approach in the analysis of local search heuristics
