On the Approximability of the Traveling Salesman Problem with Line Neighborhoods

We study the variant of the Euclidean Traveling Salesman problem where instead of a set of points, we are given a set of lines as input, and the goal is to find the shortest tour that visits each line. The best known upper and lower bounds for the problem in $mathbb{R}^d$, with $dge 3$, are $mathrm{NP}$-hardness and an $O(log^3 n)$-approximation algorithm which is based on a reduction to the group Steiner tree problem. We show that TSP with lines in $mathbb{R}^d$ is APX-hard for any $dge 3$. More generally, this implies that TSP with $k$-dimensional flats does not admit a PTAS for any $1le k leq d-2$ unless $mathrm{P}=mathrm{NP}$, which gives a complete classification of the approximability of these problems, as there are known PTASes for $k=0$ (i.e., points) and $k=d-1$ (hyperplanes). We are able to give a stronger inapproximability factor for $d=O(log n)$ by showing that TSP with lines does not admit a $(2-epsilon)$-approximation in $d$ dimensions under the unique games conjecture. On the positive side, we leverage recent results on restricted variants of the group Steiner tree problem in order to give an $O(log^2 n)$-approximation algorithm for the problem, albeit with a running time of $n^{O(loglog n)}$.

Vertex Sparsification for Edge Connectivity

Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether $(1+epsilon)$-approximate cut-preserving vertex sparsifiers with size close to the number of terminals exist. As a step towards this goal, we study a thresholded version of the problem: for a given parameter $c$, find a smaller graph, which we call connectivity-$c$ mimicking network, which preserves connectivity among $k$ terminals exactly up to the value of $c$. We show that connectivity-$c$ mimicking networks with $O(kc^4)$ edges exist and can be found in time $m(clog n)^{O(c)}$. We also give a separate algorithm that constructs such graphs with $k cdot O(c)^{2c}$ edges in time $mc^{O(c)}log^{O(1)}n$. These results lead to the first data structures for answering fully dynamic offline $c$-edge-connectivity queries for $c ge 4$ in polylogarithmic time per query, as well as more efficient algorithms for survivable network design on bounded treewidth graphs.

Mimicking Networks Parameterized by Connectivity

Given a graph $G=(V,E)$, capacities $w(e)$ on edges, and a subset of terminals $mathcal{T} subseteq V: |mathcal{T}| = k$, a mimicking network for $(G,mathcal{T})$ is a graph $(H,w)$ that contains copies of $mathcal{T}$ and preserves the value of minimum cuts separating any subset $A, B subseteq mathcal{T}$ of terminals. Mimicking networks of size $2^{2^k}$ are known to exist and can be constructed algorithmically, while the best known lower bound is $2^{Omega(k)}$; therefore, an exponential size is required if one aims at preserving cuts exactly. In this paper, we study mimicking networks that preserve connectivity of the graph exactly up to the value of $c$, where $c$ is a parameter. This notion of mimicking network is sufficient for some applications, as we will elaborate. We first show that a mimicking of size $3^c cdot k$ exists, that is, we can preserve cuts with small capacity using a network of size linear in $k$. Next, we show an algorithm that finds such a mimicking network in time $2^{O(c^2)} operatorname{poly}(m)$.

Finding All Useless Arcs in Directed Planar Graphs

We present a linear-time algorithm for simplifying flow networks on directed planar graphs: Given a directed planar graph on $n$ vertices, a source vertex $s$ and a sink vertex $t$, our algorithm removes all the arcs that do not participate in any simple $s,t$-path in linear-time. The output graph produced by our algorithm satisfies the prerequisite needed by the $O(nlog n)$-time algorithm of Weihe [FOCS94 & JCSS97] for computing maximum $s,t$-flow in directed planar graphs. Previously, Weihes algorithm could not run in $O(nlog n)$-time due to the absence of the preprocessing step; all the preceding algorithms run in $tilde{Omega}(n^2)$-time [Misiolek-Chen, COCOON05 & IPL06; Biedl, Brejov{{a}} and Vinar, MFCS00]. Consequently, this provides an alternative $O(nlog n)$-time algorithm for computing maximum $s,t$-flow in directed planar graphs in addition to the known $O(nlog n)$-time algorithms [Borradaile-Klein, SODA06 & J.ACM09; Erickson, SODA10]. Our algorithm can be seen as a (truly) linear-time $s,t$-flow sparsifier for directed planar graphs, which runs faster than any maximum $s,t$-flow algorithm (which can also be seen of as a sparsifier). The simplified structures of the resulting graph might be useful in future developments of maximum $s,t$-flow algorithms in both directed and undirected planar graphs.

Faster Algorithms for Semi-Matching Problems

We consider the problem of finding textit{semi-matching} in bipartite graphs which is also extensively studied under various names in the scheduling literature. We give faster algorithms for both weighted and unweighted case. For the weighted case, we give an $O(nmlog n)$-time algorithm, where $n$ is the number of vertices and $m$ is the number of edges, by exploiting the geometric structure of the problem. This improves the classical $O(n^3)$ algorithms by Horn [Operations Research 1973] and Bruno, Coffman and Sethi [Communications of the ACM 1974]. For the unweighted case, the bound could be improved even further. We give a simple divide-and-conquer algorithm which runs in $O(sqrt{n}mlog n)$ time, improving two previous $O(nm)$-time algorithms by Abraham [MSc thesis, University of Glasgow 2003] and Harvey, Ladner, Lovasz and Tamir [WADS 2003 and Journal of Algorithms 2006]. We also extend this algorithm to solve the textit{Balance Edge Cover} problem in $O(sqrt{n}mlog n)$ time, improving the previous $O(nm)$-time algorithm by Harada, Ono, Sadakane and Yamashita [ISAAC 2008].