Search

Among various variants of the traveling salesman problem (TSP), the s-t-path graph TSP has the special feature that we know the exact integrality ratio, 3 2, and an approximation algorithm matching this ratio. In this paper, we go below this threshold: we devise a polynomialtime algorithm for the s-t-path graph TSP with approximation ratio 1.497. Our algorithm can be viewed as a refinement of the 3 2 -approximation algorithm in [A. SebH o and J. Vygen, Combinatorica, 34 (2014), pp. 597--629], but we introduce several completely new techniques. These include a new type of ear-decomposition, an enhanced ear induction that reveals a novel connection to matroid union, a stronger lower bound, and a reduction of general instances to instances in which s and t have small distance (which works for general metrics). [ABSTRACT FROM AUTHOR]

The matrix spectral norm and nuclear norm appear in enormous applications. The generalization of these norms to higher-order tensors is becoming increasingly important, but unfortunately they are NP-hard to compute or even approximate. Although the two norms are dual to each other, the best-known approximation bound achieved by polynomial-time algorithms for the tensor nuclear norm is worse than that for the tensor spectral norm. In this paper, we bridge this gap by proposing deterministic algorithms with the best bound for both tensor norms. Our methods not only improve the approximation bound for the nuclear norm but also are data independent and easily implementable compared to existing approximation methods for the tensor spectral norm. The main idea is to construct a selection of unit vectors that can approximately represent the unit sphere, in other words, a collection of spherical caps to cover the sphere. For this purpose, we explicitly construct several collections of spherical caps for sphere covering with adjustable parameters for different levels of approximations and cardinalities. These readily available constructions are of independent interest, as they provide a powerful tool for various decision-making problems on spheres and related problems. We believe the ideas of constructions and the applications to approximate tensor norms can be useful to tackle optimization problems over other sets, such as the binary hypercube. [ABSTRACT FROM AUTHOR]

We study geometric duality for convex vector optimization problems. For a primal problem with a q-dimensional objective space, we formulate a dual problem with a (q+1)-dimensional objective space. Consequently, different from an existing approach, the geometric dual problem does not depend on a fixed direction parameter, and the resulting dual image is a convex cone. We prove a one-to-one correspondence between certain faces of the primal and dual images. In addition, we show that a polyhedral approximation for one image gives rise to a polyhedral approximation for the other. Based on this, we propose a geometric dual algorithm which solves the primal and dual problems simultaneously and is free of direction-biasedness. We also modify an existing direction-free primal algorithm in such a way that it solves the dual problem as well. We test the performance of the algorithms for randomly generated problem instances by using the so-called primal error and hypervolume indicator as performance measures. [ABSTRACT FROM AUTHOR]

We consider the consensus interdiction problem (CIP), in which the goal is to maximize the convergence time of consensus averaging dynamics subject to removing a limited number of network edges. We first show that CIP can be cast as an effective resistance interdiction problem (ERIP), in which the goal is to remove a limited number of network edges to maximize the effective resistance between a source node and a sink node. We show that ERIP is strongly NP-hard, even for bipartite graphs of diameter three with fixed source/sink edges, and establish the same hardness result for the CIP. We then show that both ERIP and CIP cannot be approximated up to a (nearly) polynomial factor assuming the exponential time hypothesis. Subsequently, we devise a polynomialtime mn-approximation algorithm for the ERIP that only depends on the number of nodes n and the number of edges m but is independent of the size of edge resistances. Finally, using a quadratic program formulation for the CIP, we devise an iterative approximation algorithm to find a first-order stationary solution for the CIP and evaluate its good performance through numerical experiments. [ABSTRACT FROM AUTHOR]

We revisit Min-Mean-Cycle, the classical problem of finding a cycle in a weighted directed graph with minimum mean weight. Despite an extensive algorithmic literature, previous work failed to achieve a near-linear runtime in the number of edges m. We propose an algorithm with near-linear runtime Õ(m(Wmax/ε)²) for computing an e additive approximation on graphs with polylogarithmic diameter and weights of magnitude at most Wmax. In particular, this is the first algorithm whose runtime scales in the number of vertices n as Õ(n²) for the complete graph. Moreover--unconditionally on the diameter--the algorithm uses only O(n) memory beyond reading the input, making it "memory-optimal". Our approach is based on solving a linear programming (LP) relaxation using entropic regularization, which reduces the LP to a Matrix Balancing problem--à la the popular reduction of Optimal Transport to Matrix Scaling. We then round the fractional LP solution using a variant of the classical Cycle-Canceling algorithm that is sped up to near-linear runtime at the expense of being approximate, and implemented in a memory-optimal manner. The algorithm is simple to implement and is competitive with the state-of-the-art methods in practice. [ABSTRACT FROM AUTHOR]

Maximizing a monotone submodular function under various constraints is a classical and intensively studied problem. However, in the single-pass streaming model, where the elements arrive one by one and an algorithm can store only a small fraction of input elements, there is large gap in our knowledge, even though several approximation algorithms have been proposed in the literature. In this work, we present the first lower bound on the approximation ratios for cardinality and matroid constraints that beat 1- 1 e in the single-pass streaming model. Let n be the number of elements in the stream. Then, we prove that any (randomized) streaming algorithm for a cardinality constraint with approximation ratio 2- v 2+e requires O(n K2) space for any e > 0, where K is the size limit of the output set. We also prove that any (randomized) streaming algorithm for a (partition) matroid constraint with approximation ratio K 2K-1 + e requires O(n K2) space for any e > 0, where K is the rank of the given matroid. In addition, we give streaming algorithms that assume access to the objective function via a weak oracle that can only be used to evaluate function values on feasible sets. Specifically, we show weak-oracle streaming algorithms for cardinality and matroid constraints with approximation ratios K 2K-1 and 1 2, respectively, whose space complexity is exponential in K but is independent of n. The former one exactly matches the known inapproximability result for a cardinality constraint in the weak oracle model. The latter one almost matches our lower bound of K 2K-1 for a matroid constraint, which almost settles the approximation ratio for a matroid constraint that can be obtained by a streaming algorithm whose space complexity is independent of n. [ABSTRACT FROM AUTHOR]

Fundamental in matrix algebra and its applications, a generalized inverse of a real matrix A is a matrix H that satisfies the Moore--Penrose (M--P) property AH A = A. If H also satisfies the additional useful M--P property, H AH = H, it is called a reflexive generalized inverse. Reflexivity is equivalent to minimum rank, so we are particularly interested in reflexive generalized inverses. We consider aspects of symmetry related to the calculation of a sparse reflexive generalized inverse of A. As is common, and following Fampa and Lee [Oper. Res. Lett., 46 (2018), pp. 605-610] for calculating sparse generalized inverses, we use (vector) 1-norm minimization for inducing sparsity and for keeping the magnitude of entries under control. When A is symmetric, we may naturally desire a symmetric H, while generally such a restriction on H may not lead to a 1-norm minimizing reflexive generalized inverse. We investigate a block construction method to produce a symmetric reflexive generalized inverse that is structured and has guaranteed sparsity. We provide a theoretically efficient and practical local-search algorithm to block construct an approximate 1-norm minimizing symmetric reflexive generalized inverse. Another aspect of symmetry that we consider relates to another M--P property: H is ah-symmetric if AH is symmetric. The ah-symmetry property is the key one for solving least-squares problems using H. Here we do not assume that A is symmetric, and we do not impose symmetry on H. We investigate a column block construction method to produce an ah-symmetric reflexive generalized inverse that is structured and has guaranteed sparsity. We provide a theoretically efficient and practical local-search algorithm to column block construct an approximate 1-norm minimizing ah-symmetric reflexive generalized inverse. [ABSTRACT FROM AUTHOR]

We devise a constant-factor approximation algorithm for the maximization version of the edge-disjoint paths problem if the supply graph together with the demand edges forms a planar graph. By planar duality, this is equivalent to packing cuts in a planar graph such that each cut contains exactly one demand edge. We also show that the natural linear programming relaxations have constant integrality gap, yielding an approximate max-multiflow min-multicut theorem. [ABSTRACT FROM AUTHOR]

Sparse regression and variable selection for large-scale data have been rapidly developed in the past decades. This work focuses on sparse ridge regression, which enforces the sparsity by use of the L0 norm. We first prove that the continuous relaxation of the mixed integer second order conic (MISOC) reformulation using perspective formulation is equivalent to that of the convex integer formulation proposed in recent work. We also show that the convex hull of the constraint system of the MISOC formulation is equal to its continuous relaxation. Based upon these two formulations (i.e., the MISOC formulation and convex integer formulation), we analyze two scalable algorithms, the greedy and randomized algorithms, for sparse ridge regression with desirable theoretical properties. The proposed algorithms are proved to yield near-optimal solutions under mild conditions. We further propose integrating the greedy algorithm with the randomized algorithm, which can greedily search the features from the nonzero subset identified by the continuous relaxation of the MISOC formulation. The merits of the proposed methods are illustrated through numerical examples in comparison with several existing ones. [ABSTRACT FROM AUTHOR]

Clustering is a classic topic in optimization with k-means being one of the most fundamental such problems. In the absence of any restrictions on the input, the best known algorithm for k-means with a provable guarantee is a simple local search heuristic yielding an approximation guarantee of 9+ϵ, a ratio that is known to be tight with respect to such methods. We overcome this barrier by presenting a new primal-dual approach that allows us to (1) exploit the geometric structure of k-means and (2) to satisfy the hard constraint that at most k clusters are selected without deteriorating the approximation guarantee. Our main result is a 6.357-approximation algorithm with respect to the standard LP relaxation. Our techniques are quite general and we also show improved guarantees for the general version of k-means where the underlying metric is not required to be Euclidean and for k-median in Euclidean metrics. [ABSTRACT FROM AUTHOR]

Motivated by emerging resource allocation and data placement problems such as web caches and peer-to-peer systems, we consider and study a class of resource allocation problems over a network of agents (nodes). In this model, which can be viewed as a homogeneous data placement problem, nodes can store only a limited number of resources while accessing the remaining ones through their closest neighbors. We consider this problem under both optimization and gametheoretic frameworks. In the case of optimal resource allocation, we will first show that when there are only k = 2 resources, the optimal allocation can be found efficiently in O(n ² log n) steps, where n denotes the total number of nodes. However, for k \geq 3 this problem becomes NP-hard with no polynomial-time approximation algorithm with a performance guarantee better than 1 + 1 102k², even under metric access costs. We then provide a 3-approximation algorithm for the optimal resource allocation which runs only in O(kn² ). Subsequently, we look at this problem under a selfish setting formulated as a noncooperative game and provide a 3-approximation algorithm for obtaining its pure Nash equilibria under metric access costs. We then establish an equivalence between the set of pure Nash equilibria and flip-optimal solutions of the Max-k-Cut problem over a specific weighted complete graph. While this reduction suggests that finding a pure Nash equilibrium using best response dynamics might be PLS-hard, it allows us to use tools from complementary slackness and quadratic programming to devise systematic and more efficient algorithms towards obtaining Nash equilibrium points. [ABSTRACT FROM AUTHOR]

In this paper, we show that every (2P2, K4)-free graph is 4-colorable. The bound is attained by the five-wheel and the complement of the seven-cycle. This answers an open question by Wagon [J. Combin. Theory Ser. B, 29 (1980), pp. 345-346] from the 1980s. Our result can also be viewed as a result in the study of the Vizing bound for graph classes. A major open problem in the study of computational complexity of graph coloring is whether coloring can be solved in polynomial time for (4P1,C4)-free graphs. Lozin and Malyshev [Discrete Appl. Math., 216 (2017), pp. 273-280] conjecture that the answer is yes. As an application of our main result, we provide the first positive evidence to the conjecture by giving a 2-approximation algorithm for coloring (4P1,C4)-free graphs. [ABSTRACT FROM AUTHOR]

We study the mathematical concept of the strength of a graph as defined by Cunningham to partition very large graphs. The strength is the objective value of an attack problem on a graph where the striker aims at dividing the graph into a maximum number of connected components removing as few edges as possible per component uncoupled. The strength is the optimal number of edges per component uncoupled or, in the weighted version, the sum of the weights of the edges removed per component uncoupled. Given a connected graph with n vertices and m weighted edges, we denote by W the total sum of the integer weights, and we describe an algorithm that approximates within a factor of 1+ε the weighted strength in time O(mlog(W)log³(n)/ε²), and that can be implemented with O(m) memory use if we allow a complexity of O(mlog²(W)log³(n)/ε²). This result has several important applications, in particular for the detection of dense areas of a graph, in terms of weighted edges, which in turn can be used for spam detection, community identification, and partitioning. [ABSTRACT FROM AUTHOR]

The Chordal Vertex Deletion (CHVD) problem asks to delete a minimum number of vertices from an input graph to obtain a chordal graph. In this paper we develop a polynomial kernel for CHVD under the parameterization by the solution size. Using a new Erdõs-Pósa-type packing/covering duality for holes in nearly chordal graphs, we present a polynomial-time algorithm that reduces any instance (G, k) of CHVD to an equivalent instance with poly(k) vertices. The existence of a polynomial kernel answers an open problem posed by Marx in 2006 [D. Marx, "Chordal Deletion Is Fixed-Parameter Tractable," in Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci. 4271, Springer, 2006, pp. 37-48]. To obtain the kernelization, we develop the first poly(opt)-approximation algorithm for CHVD, which is of independent interest. In polynomial time, it either decides that G has no chordal deletion set of size k, or outputs a solution of size O(k4log² k). [ABSTRACT FROM AUTHOR]

We consider the following geometric optimization problem: find a convex polygon of maximum area contained in a given simple polygon P with n vertices. We give a randomized near- linear-time (1 - ε)-approximation algorithm for this problem: in O(n(log² n + (1/ε³) log n + 1=ε4) time we find a convex polygon contained in P that, with probability at least 2=3, has area at least (1 - ε) times the area of an optimal solution. We also obtain similar results for the variant of computing a convex polygon inside P with maximum perimeter. To achieve these results we provide new results in geometric probability. The first result is a bound relating the area of the largest convex body inside P to the probability that two points chosen uniformly at random inside P are mutually visible. The second result is a bound on the expected value of the difference between the perimeter of any planar convex body K and the perimeter of the convex hull of a uniform random sample inside K. [ABSTRACT FROM AUTHOR]

We present a 10/7 -approximation algorithm for the minimum 2-vertex-connected spanning subgraph problem. Similarly to the work of Cheriyan, Sebö, and Szigeti for 2-edge-connected spanning subgraphs, our algorithm is based on computing a carefully designed ear-decomposition. [ABSTRACT FROM AUTHOR]

We consider the following single-machine scheduling problem, which is often denoted 1||∑ fj: we are given n jobs to be scheduled on a single machine, where each job j has an integral processing time pj, and there is a nondecreasing, nonnegative cost function fj (Cj) that specifies the cost of finishing j at time Cj; the objective is to minimize ∑j=1n fj (Cj). Bansal and Pruhs recently gave the first constant approximation algorithm with a performance guarantee of 16. We improve on this result by giving a primal-dual pseudo-polynomial-time algorithm based on the recently introduced knapsack-cover inequalities. The algorithm finds a schedule of cost at most four times the constructed dual solution. Although we show that this bound is tight for our algorithm, we leave open the question of whether the integrality gap of the linear program is less than 4. Finally, we show how the technique can be adapted to yield, for any ∈ > 0, a polynomial time (4 + ∈)-approximation algorithm for this problem. [ABSTRACT FROM AUTHOR]

Let G = (V, E) be a simple graph of maximum degree Δ. The edges of G can be colored with at most Δ + 1 colors by Vizing's theorem. We study lower bounds on the size of subgraphs of G that can be colored with A colors. Vizing's theorem gives a bound of Δ/Δ + 1 |E|. This is known to be tight for cliques κΔ + 1 when Δ is even. However, for Δ = 3 it was improved to 26/31 |E| by Albertson and Haas [Discrete Math., 148 (1996), pp. 1-7] and later to 6/7|E| by Rizzi [Discrete Math., 309 (2009), pp. 4166-4170]. It is tight for B3, the graph isomorphic to a K4 with one edge subdivided. We improve previously known bounds for Δ ∈ {3,..., 7}, under the assumption that for Δ = 3,4,6, graph G is not isomorphic to B3, K5, and K7, respectively. For Δ ≥ 4 these are the first results which improve over the Vizing's bound. We also show a new bound for subcubic multigraphs not isomorphic to K3 with one edge doubled. In the second part, we give approximation algorithms for the maximum κ-edge-colorable subgraph problem, where given a graph G (without any bound on its maximum degree or other restrictions) one has to find a κ-edge-colorable subgraph with the maximum number of edges. In particular, when G is simple for κ = 3, 4, 5, 6, 7 we obtain approximation ratios of 13/15, 9/11, 19/22, 23/27, and 22/25, respectively. We also present a 7/9-approximation for κ = 3 when G is a multigraph. The approximation algorithms follow from a new general framework that can be used for any value of κ. [ABSTRACT FROM AUTHOR]

The c-pumpkin is the graph with two vertices linked by c ≥ 1 parallel edges. A c-pumpkin-model in a graph G is a pair {A, B} of disjoint subsets of vertices of G, each inducing a connected subgraph of G, such that there are at least c edges in G between A and B. We focus on hitting and packing c-pumpkin-models in a given graph in the realm of approximation algorithms and parameterized algorithms. We give a fixed-parameter tractable (FPT) algorithm running in time 2...(κ)(n...(1) deciding, for any fixed c ≥ 1, whether all c-pumpkin-models can be hit by at most k vertices. This generalizes known single-exponential FPT algorithms for Vertex Cover and Feedback Vertex SET, which correspond to the cases c = 1, 2 respectively. Finally, we present an ...(log n)-approximation algorithm for both the problems of hitting all c-pumpkin-models with a smallest number of vertices and packing a maximum number of vertex-disjoint c-pumpkin-models. [ABSTRACT FROM AUTHOR]

We present an approximation algorithm for the shortest descending path problem. Given a source s and a destination t on a terrain, a shortest descending path from s to t is a path of minimum Euclidean length on the terrain subject to the constraint that the height decreases monotonically as we traverse that path from s to t. Given any ε ∈ (0, 1), our algorithm returns in O(n4 log(n/ε)) time a descending path of length at most 1 + ε times the optimum. This is the first algorithm whose running time is polynomial in n and log(1/ε) and independent of the terrain geometry. [ABSTRACT FROM AUTHOR]

Minimum-weight triangulation (MWT) is NP-hard. It has a polynomial-time constant-factor approximation algorithm, and a variety of effective polynomial-time heuristics that, for many instances, can find the exact MWT. Linear programs (LPs) for MWT are well-studied, but previously no connection was known between any LP and any approximation algorithm or heuristic for MWT. Here we show the first such connections: For an LP formulation due to Dantzig, Hoffman, and Hu [Math. Programming, 31 (1985), pp. 1-14], (i) the integrality gap is constant, and (ii) given any instance, if the aforementioned heuristics find the MWT, then so does the LP. [ABSTRACT FROM AUTHOR]

Given an undirected, capacitated graph G = (V, E) and a set K ⊂ V of terminals of size k, we construct an undirected, capacitated graph G' = (K, E') for which the cut function approximates the value of every minimum cut separating any subset U of terminals from the remaining terminals K - U. We refer to this graph G' as a cut-sparsifier, and we prove that there are cut-sparsifiers that can approximate all these minimum cuts in G to within an approximation factor that depends only polylogarithmically on k, the number of terminals. We prove such cut-sparsifiers exist through a zero-sum game, and we construct such sparsifiers through oblivious routing guarantees. These results allow us to derive a more general theory of Steiner cut and flow problems, and allow us to obtain approximation algorithms with guarantees independent of the size of the graph for a number of graph partitioning, graph layout, and multicommodity flow problems for which such guarantees were previously unknown. [ABSTRACT FROM AUTHOR]

We study the problem of computing correlation between two piecewise-linear bivariate functions defined over a common domain, where the surfaces they define in three dimensions--polyhedral terrains--can be transformed vertically by a linear transformation of the third coordinate (scaling and translation). We present a randomized algorithm that minimizes the maximum vertical distance between the graphs of the two functions, over all linear transformations of one of the terrains, in O(n4/3 polylog n) expected time, where n is the total number of vertices in the graphs of the two functions. We also present approximation algorithms for minimizing the mean distance between the graphs of univariate and bivariate functions. For univariate functions we present a (1 + ε)-approximation algorithm that runs in O(n(1 +log²(1/ε))) expected time for any fixed ε > 0. The (1 + ε)-approximation algorithm for bivariate functions runs in O(n/ε) time, for any fixed ε > 0, provided the two functions are defined over the same triangulation of their domain. [ABSTRACT FROM AUTHOR]

We present an O(log² k)-approximation algorithm for the problem of finding a k-vertex connected spanning subgraph of minimum cost, where n is the number of vertices in an input graph, and k is a connectivity requirement. Our algorithm is the first that achieves a polylog-arithmic approximation ratio for all values of k and n, and it works for both directed and undirected graphs. As in previous works, we use the Frank-Tardos algorithm for finding k-outconnected subgraphs as a subroutine. However, with our structural lemmas, we are able to show that we need only partial solutions returned by the Frank-Tardos algorithm; thus, we can avoid paying the whole cost of an optimal solution every time the algorithm is applied. [ABSTRACT FROM AUTHOR]

Since the celebrated work of Jerrum, Sinclair, and Vigoda [J. ACM, 51 (2004), pp. 671--697], we have known that the permanent of a matrix with entries in {0, 1} can be approximated in randomized polynomial time by using a rapidly mixing Markov chain to sample perfect matchings of a bipartite graph. A separate strand of the literature has pursued the possibility of an alternate, algebraic polynomial-time approximation scheme. These schemes work by replacing each 1 with a random element of an algebra A and considering the determinant of the resulting matrix. In the case where A is noncommutative, this determinant can be defined in several ways. We show that for some estimators based on the conventional determinant, the critical ratio of the second moment to the square of the first--and therefore the number of trials we need to obtain a good estimate of the permanent--is (1 + O(1/d))n when A is the algebra of d X d matrices. These results can be extended to group algebras and semisimple algebras in general. We also study the symmetrized determinant of Barvinok, showing that the resulting estimator has small variance when d is large enough. However, if d is constant--the only case in which an efficient algorithm is known--we show that the critical ratio exceeds 2n/nO(d). Thus our results do not provide a new polynomial-time approximation scheme for the permanent. Indeed, they suggest that the algebraic approach to approximating the permanent faces significant obstacles. We obtain these results using diagrammatic techniques in which we express matrix products as contractions of tensor products. When these matrices are chosen randomly according to the Gaussian distribution, we can evaluate the trace of these products in terms of the cycle structure of a suitably random permutation. In the symmetrized case, our estimates are then derived by a connection with the character theory of the symmetric group. [ABSTRACT FROM AUTHOR]

Only recently Goyal, Olver, and Shepherd [PToc. STOC, ACM, New York, 2008] proved that the symmetric virtual private network design (sVPN) problem has the tree routing property, namely, that there always exists all optimal solution to the problem whose support is a tree. Combining this with previous results by Fingerhut, Suri, and Turner [J. Algorithms. 24 (1997), pp. 287-309] and Gupta et al. [Proc. STOC, ACM, New York, 2001], sVPN can be solved in polynomial time. In this paper we investigate an APX-hard generalization of sVPn, where the contribution of each edge to the total cost is proportional to some non-negative, concave, and nondecreasing function of the capacity reservation. We show that the tree routing property extends to the new problem and give a constant-factor approximation algorithm for it. We also show that the undirected uncapacitated single-source minimum concave-cost flow problem has the tree routing property when the cost function has some property of symmetry. [ABSTRACT FROM AUTHOR]

Multicommodity facility location refers to the extension of facility location to allow for different clients' demands for different goods from among a finite set of goods. This leads to several optimization problems, depending on the cost of opening a facility (now a function of the commodities it serves). In this paper, we introduce and provide approximation algorithms for two fairly general versions of multicommodity facility location. We formulate integer programming models for these problems, and use them to provide approximation algorithms for the problems that are close to the inapproximability thresholds. [ABSTRACT FROM AUTHOR]

The vertex cover problem is a classical NP–complete problem for which the best worstcase approximation ratio is 2–o(1). In this paper, we use a collection of simple graph transformations, each of which guarantees an approximation ratio of 3 2 , to find approximate vertex covers for a large collection of randomly generated graphs and test graphs from various sources. The graph reductions are extremely fast, and even though they by themselves are not guaranteed to find a vertex cover, we manage to find a 3 2 –approximate vertex cover for almost every single graph in our collection. The few graphs that we cannot solve have specific structure: they are triangle–free, with a minimum degree of at least 3, a lower bound of n 2 on the optimal vertex cover, and are unlikely to have a large bipartite subgraph. [ABSTRACT FROM AUTHOR]

We give a 7.18-approximation algorithm for the minimum latency problem that uses only O(n log n) calls to the prize-collecting Steiner tree (PCST) subroutine of Goemans and Williamson. This improves the previous best algorithms in both performance guarantee and running time. A previous algorithm of Goemans and Kleinberg for the minimum latency problem requires an approximation algorithm for the k-minimum spanning tree (k-MST) problem which is called as a black box for each value of k. Their algorithm can achieve an approximation factor of 10.77 while making O(n(n + log C) log n) PCST calls, a factor of 8.98 using O(n³ (n + log C) log n) PCST calls, or a factor of 7.18 + ϵ using nO(1/ϵ) log C PCST calls, via the k-MST algorithms of Garg, Arya and Ramesh, and Arora and Karakostas, respectively. Here n denotes the number of nodes in the instance, and C is the largest edge cost in the input. In all cases, the running time is dominated by the PCST calls. Since the PCST subroutine can be implemented to run in O(n²) time, the overall running time of our algorithm is O(n³ log n). We also give a faster randomized version of our algorithm that achieves the same approximation guarantee in expectation, but uses only O(log² n) PCST calls, and derandomize it to obtain a deterministic algorithm with factor 7.18 + ϵ, using O( 1/ϵ log² n) PCST calls. The basic idea for our improvement is that we do not treat the k-MST algorithm as a black box. This allows us to take advantage of some special situations in which the PCST subroutine delivers a 2-approximate k-MST. We are able to obtain the same approximation ratio that would be given by Goemans and Kleinberg if we had access to 2-approximate k-MSTs for all values of k, even though we have them only for some values of k that we are not able to specify in advance. We also extend our algorithm to a weighted version of the minimum latency problem. [ABSTRACT FROM AUTHOR]