Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth

I present a nearly linear work parallel algorithm for approximating the Held-Karp bound for the Metric TSP problem. Given an edge-weighted undirected graph G=(V,E) on m edges and ϵ>0, it returns a (1+ϵ)-approximation to the Held-Karp bound with high probability, in Õ (m/(ϵ^4)) work and Õ (1/(ϵ^4)) depth. While a nearly linear time sequential algorithm was known for almost a decade (Chekuri and Quanrud'17), it was not known how to simultaneously achieve nearly linear work alongside polylogarithmic depth. Using a reduction by Chalermsook et al.'22, we also give a parallel algorithm for computing a (1+ϵ)-approximate fractional solution to the k-edge-connected spanning subgraph (kECSS) problem, with the same complexity. To obtain these results, we introduce a notion of core-sequences for the parallel Multiplicative Weights Update (MWU) framework (Luby-Nisan'93, Young'01). For the Metric TSP and kECSS problems, core-sequences enable us to exploit the structure of approximate minimum cuts to reduce the cost per iteration and/or the number of iterations. The acceleration technique via core-sequences is generic and of independent interest. In particular, it improves the best-known iteration complexity of MWU algorithms for packing/covering LPs from poly(lognnz(A)) to polylogarithmic in the product of cardinalities of the core-sequence sets where A is the constraint matrix of the LP. For certain implicitly defined LPs such as the kECSS LP, this yields an exponential improvement in depth.