We give a nearly linear time randomized approximation scheme for the Held-Karp bound [Held and Karp, 1970] for metric TSP. Formally, given an undirected edge-weighted graph @math on @math edges and @math , the algorithm outputs in @math time, with high probability, a @math -approximation to the Held-Karp bound on the metric TSP instance induced by the shortest path metric on @math . The algorithm can also be used to output a corresponding solution to the Subtour Elimination LP. We substantially improve upon the @math running time achieved previously by Garg and Khandekar. The LP solution can be used to obtain a fast randomized @math -approximation for metric TSP which improves upon the running time of previous implementations of Christofides' algorithm.
Our work here builds extensively on Karger's randomized nearly linear time mincut algorithm @cite_0 . As mentioned already, we adapt his algorithm to a partially dynamic setting informed by the MWU framework. also builds on Karger's tree packing ideas to develop a dynamic mincut algorithm. Thorup's algorithm is rather involved and is slower than what we are able to achieve for the partial dynamic setting; he achieves an update time of @math while we achieve polylogarithmic time. There are other obstacles to integrating his ideas and data structure to the needs of the MWU framework as we already remarked. For unweighted incremental mincut, recently developed a deterministic data structure with a poly-logarithmic amortized update time.
@cite_0
1964510837
We significantly improve known time bounds for solving the minimum cut problem on undirected graphs. We use a "semiduality" between minimum cuts and maximum spanning tree packings combined with our previously developed random sampling techniques. We give a randomized (Monte Carlo) algorithm that finds a minimum cut in an m -edge, n -vertex graph with high probability in O (m log 3 n ) time. We also give a simpler randomized algorithm that finds all minimum cuts with high probability in O( m log 3 n ) time. This variant has an optimal RNC parallelization. Both variants improve on the previous best time bound of O ( n 2 log 3 n ). Other applications of the tree-packing approach are new, nearly tight bounds on the number of near-minimum cuts a graph may have and a new data structure for representing them in a space-efficient manner.