Search

We study the metric s--t path traveling salesman problem (TSP). An, Kleinberg, and Shmoys [Proceedings of the 44th ACM Symposium on Theory of Computing, 2012, pp. 875-886] improved on the long-standing 5/3 -approximation factor and presented an algorithm that achieves an approximation factor of 1+√5/2 ≈ 1.61803. Later, Sebö [Proceedings of the 16th Conference on Integer Programming and Combinatorial Optimization, 2013, pp. 362-374] further improved the approximation factor to 8/5. We present a simple, self-contained analysis that unifies both results; our main contribution is a unified correction vector. Additionally, we compare two different linear programming (LP) relaxations of the s--t path TSP, namely, the path version of the Held--Karp LP relaxation for the TSP and a weaker LP relaxation, and we show that both LPs have the same (fractional) optimal value. Also, we show that the minimum cost of integral solutions of the two LPs are within a factor of 3/2 of each other. Furthermore, we prove that a half-integral solution of the stronger LP relaxation of cost c can be rounded to an integral solution of cost at most 3/2 c. Finally, we give an example that presents obstructions to two natural methods that aim for an approximation factor of 3/2. [ABSTRACT FROM AUTHOR]

Low-rank matrix approximations, such as the truncated singular value decomposition and the rank-revealing QR decomposition, play a central role in data analysis and scientific computing. This work surveys and extends recent research which demonstrates that randomization offers a powerful tool for performing low-rank matrix approximation. These techniques exploit modern computational architectures more fully than classical methods and open the possibility of dealing with truly massive data sets. This paper presents a modular framework for constructing randomized algorithms that compute partial matrix decompositions. These methods use random sampling to identify a subspace that captures most of the action of a matrix. The input matrix is then compressed--either explicitly or implicitly--to this subspace, and the reduced matrix is manipulated deterministically to obtain the desired low-rank factorization. In many cases, this approach beats its classical competitors in terms of accuracy, robustness, and/or speed. These claims are supported by extensive numerical experiments and a detailed error analysis. The specific benefits of randomized techniques depend on the computational environment. Consider the model problem of finding the k dominant components of the singular value decomposition of an m x n matrix, (i) For a dense input matrix, randomized algorithms require O(mn log (k)) floating-point operations (flops) in contrast to O(mnk) for classical algorithms, (ii) For a sparse input matrix, the flop count matches classical Krylov subspace methods, but the randomized approach is more robust and can easily be reorganized to exploit multiprocessor architectures, (iii) For a matrix that is too large to fit in fast memory, the randomized techniques require only a constant number of passes over the data, as opposed to O(k) passes for classical algorithms. In fact, it is sometimes possible to perform matrix approximation with a single pass over the data. [ABSTRACT FROM AUTHOR]

Graph coloring has been employed since the 1980s to efficiently compute sparse Jacobian and Hessian matrices using either finite differences or automatic differentiation. Several coloring problems occur in this context, depending on whether the matrix is a Jacobian or a Hessian, and on the specifics of the computational techniques employed. We consider eight variant vertex coloring problems here. This article begins with a gentle introduction to the problem of computing a sparse Jacobian, followed by an overview of the historical development of the research area. Then we present a unifying framework for the graph models of the variant matrix estimation problems. The framework is based upon the viewpoint that a partition of a matrix into structurally orthogonal groups of columns corresponds to distance-2 coloring an appropriate graph representation. The unified framework helps integrate earlier work and leads to fresh insights; enables the design of more efficient algorithms for many problems; leads to new algorithms for others; and eases the task of building graph models for new problems. We report computational results on two of the coloring problems to support our claims. Most of the methods for these problems treat a column or a row of a matrix as an atomic entity, and partition the columns or rows (or both). A brief review of methods that do not fit these criteria is provided. We also discuss results in discrete mathematics and theoretical computer science that intersect with the topics considered here. [ABSTRACT FROM AUTHOR]

Graph coloring has been employed since the 1980s to efficiently compute sparse Jacobian and Hessian matrices using either finite differences or automatic differentiation. Several coloring problems occur in this context, depending on whether the matrix is a Jacobian or a Hessian, and on the specifics of the computational techniques employed. We consider eight variant vertex coloring problems here. This article begins with a gentle introduction to the problem of computing a sparse Jacobian, followed by an overview of the historical development of the research area. Then we present a unifying framework for the graph models of the variant matrix estimation problems. The framework is based upon the viewpoint that a partition of a matrix into structurally orthogonal groups of columns corresponds to distance-2 coloring an appropriate graph representation. The unified framework helps integrate earlier work and leads to fresh insights; enables the design of more efficient algorithms for many problems; leads to new algorithms for others; and eases the task of building graph models for new problems. We report computational results on two of the coloring problems to support our claims. Most of the methods for these problems treat a column or a row of a matrix as an atomic entity, and partition the columns or rows (or both). A brief review of methods that do not fit these criteria is provided. We also discuss results in discrete mathematics and theoretical computer science that intersect with the topics considered here. [ABSTRACT FROM AUTHOR]

In this work we study the problem of clustering with respect to the diameter and the radius costs: We say that a set X of points in Rd is (k,b)-clusterable with respect to the diameter cost if X can be partitioned into k subsets (clusters) so that the distance between every pair of points in each cluster is at most b. In the case of the radius cost we require that all points that belong to the same cluster be at a distance of at most b for some common central point. Here we approach the problem of clustering from within the framework of property testing. In property testing, the goal is to determine whether a given object has a particular property or whether it should be modified significantly so that it obtains the property. In the context of clustering, testing takes on the following form: The algorithm is given parameters k, b, β ,and ε and it can sample from the set of points X. The goal of the algorithm is to distinguish between the case when X is (k,b)-clusterable and the case when X is ε-far from being (k, (1 +β)b )-clusterable. By ε-far from being (k,(1 +β )b )-clusterable we mean that more than ε · |X| points should be remove from X so that it becomes (k,(1 +β )b )-clusterable. In this work we describe and analyze algorithms that use a sample of size polynomial in k and 1 /ε and independent of |X|. (The dependence on β and on the dimension, d, of the points varies with the different algorithms.) Such algorithms may be especially useful when the set of points X is very large and it may not even be feasible to observe all of it. Our algorithms can also be used to find approximately good clusterings. Namely, these are clusterings of all but an ε-fraction of the points in X that have optimal (or close to optimal) cost. The benefit of our algorithms is that they construct an implicit representation of such clusterings in time independent of |X|... [ABSTRACT FROM AUTHOR]