411 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
Probabilistic Analysis of Optimization Problems on Sparse Random Shortest Path Metrics
Full text linkSimple heuristics for (combinatorial) optimization problems often show a remarkable performance in practice. Worst-case analysis often falls short of explaining this performance. Because of this, "beyond worst-case analysis" of algorithms has recently gained a lot of attention, including probabilistic analysis of algorithms.
The instances of many (combinatorial) optimization problems are essentially a discrete metric space. Probabilistic analysis for such metric optimization problems has nevertheless mostly been conducted on instances drawn from Euclidean space, which provides a structure that is usually heavily exploited in the analysis. However, most instances from practice are not Euclidean. Little work has been done on metric instances drawn from other, more realistic, distributions. Some initial results have been obtained in recent years, where random shortest path metrics generated from dense graphs (either complete graphs or Erdős - Rényi random graphs) have been used so far.
In this paper we extend these findings to sparse graphs, with a focus on grid graphs. A random shortest path metric is constructed by drawing independent random edge weights for each edge in the graph and setting the distance between every pair of vertices to the length of a shortest path between them with respect to the drawn weights. For such instances generated from a grid graph, we prove that the greedy heuristic for the minimum distance maximum matching problem, and the nearest neighbor and insertion heuristics for the traveling salesman problem all achieve a constant expected approximation ratio. Additionally, for instances generated from an arbitrary sparse graph, we show that the 2-opt heuristic for the traveling salesman problem also achieves a constant expected approximation ratio
On Approximating Multi-Criteria TSP
Full text linkWe present approximation algorithms for almost all variants of the multi-criteria traveling salesman problem (TSP), whose performances are independent of the number of criteria and come close to the approximation ratios obtained for TSP with a single objective function.
We present randomized approximation algorithms for multi-criteria maximum traveling salesman problems (Max-TSP). For multi-criteria Max-STSP, where the edge weights have to be symmetric, we devise an algorithm that achieves an approximation ratio of . For multi-criteria Max-ATSP, where the edge weights may be asymmetric, we present an algorithm with an approximation ratio of . Our algorithms work for any fixed number of objectives. To get these ratios, we introduce a decomposition technique for cycle covers. These decompositions are optimal in the sense that no decomposition can always yield more than a fraction of and , respectively, of the weight of a cycle cover. Furthermore, we present a deterministic algorithm for bi-criteria Max-STSP\ that achieves an approximation ratio of .
Finally, we present a randomized approximation algorithm for the asymmetric multi-criteria minimum TSP with triangle inequality (Min-ATSP). This algorithm achieves a ratio of . For this variant of multi-criteria TSP, this is the first approximation algorithm we are aware of. If the distances fulfil the -triangle inequality, its ratio is
Smoothed analysis of binary search trees and quicksort under additive noise
Full text linkBinary search trees are a fundamental data structure and their height plays a key role in the analysis of divide-and-conquer algorithms like quicksort. Their worst-case height is linear; their average height, whose exact value is one of the best-studied problems in average-case complexity, is logarithmic. We analyze their smoothed height under additive noise: An adversary chooses a sequence of n real numbers in the range [0, 1]; each number is individually perturbed by adding a random value from an interval of size d; and the resulting numbers are inserted into a search tree. The expected height of this tree is called smoothed tree height. If d is very small, namely for d ≤ 1/n, the smoothed tree height is the same as the worst-case height; if d is very large, the smoothed tree height approaches the logarithmic average-case height. An analysis of what happens between these extremes lies at the heart of our paper: We prove that the smoothed height of binary search trees is Θ ( � n/d + log n), where d ≥ 1/n may depend on n. This implies that the logarithmic average-case height becomes manifest only for d ∈ Ω(n / log 2 n). For the analysis, we first prove that the smoothed number of left-to-right maxima in a sequence is also Θ ( � n/d+log n). We apply these findings to the performance of the quicksort algorithm, which needs Θ(n2) comparisons in the worst case and Θ(n logn) �on average, and � prove that the n/d + n logn. This implies smoothed number of comparisons made by quicksort is Θ � n d+1 that the average-case becomes manifest already for d ∈ Ω � 3 � n / log 2 n �
Approximability of Minimum AND-Circuits
Full text linkGiven a set of monomials, the Minimum AND-Circuit problem asks for a circuit that computes these monomials using AND-gates of fan-in two and being of minimum size. We prove that the problem is not polynomial time approximable within a factor of less than 1.0051 unless P = NP, even if the monomials are restricted to be of degree at most three. For the latter case, we devise several efficient approximation algorithms, yielding an approximation ratio of 1.278. For the general problem, we achieve an approximation ratio of d − 3/2, where d is the degree of the largest monomial. In addition, we prove that the problem is fixed parameter tractable with the number of monomials as parameter. Finally, we reveal connections between the Minimum AND-Circuit problem and several problems from different areas
Proceedings of the 12th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2013) - Preface
Full text linkWorst-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
Analysis of Algorithms Beyond the Worst Case (Dagstuhl Seminar 14372)
Full text linkThis report documents the program and the outcomes of Dagstuhl Seminar 14372 "Analysis of Algorithms Beyond the Worst Case".
The theory of algorithms has traditionally focused on worst-case analysis. This focus has led to both a deep theory and many beautiful and useful algorithms. However, there are a number of important problems and algorithms for which worst-case analysis does not provide useful or empirically accurate results. This is due to the fact that worst-case inputs are often rather contrived and occur hardly ever in practical applications. Only in recent years a paradigm shift towards a more realistic and robust algorithmic theory has been initiated. The development of a more realistic theory hinges on finding models that measure the performance of an algorithm not only by its worst-case behavior but rather by its behavior on "typical" inputs. In this seminar, we discussed various recent theoretical models and results that go beyond worst-case analysis.
The seminar helped to consolidate the research and to foster collaborations among the researchers working in the different branches of analysis of algorithms beyond the worst case
Probabilistic Methods in the Design and Analysis of Algorithms (Dagstuhl Seminar 17141)
Full text linkThis report documents the program and the outcomes of Dagstuhl Seminar 17141 "Probabilistic Methods in the Design and Analysis of Algorithms".
Probabilistic methods play a central role in theoretical computer science. They are a powerful and widely applied tool used, for example, for designing efficient randomized algorithms and for establishing various lower bounds in complexity theory. They also form the basis of frameworks like average-case and smoothed analysis, in which algorithms are analyzed beyond the classical worst-case perspective. The seminar was on probabilistic methods with a focus on the design and analysis of algorithms.
The seminar helped to consolidate the research and to foster collaborations among the researchers who use probabilistic methods in different areas of the design and analysis of algorithms
- …
