Node-weighted network design and maximum sub-determinants

We consider the Node-weighted Steiner Forest problem on planar graphs. Demaine et al. showed that a generic primal-dual algorithm gives a 6-approximation. We present two different proofs of an approximation factor of~$3$. Then, we draw a connection to Goemans and Williamson who apply the primal-dual algorithm to feedback problems on planar graphs. We reduce these problems to Node-weighted Steiner Forest and show that for the graphs in the reductions their respective linear programming relaxations are equivalent to each other. This explains why both type of problems can be approximated with primal-dual methods. We show that the largest sub-determinant of a matrix $A\in Q^{d\times n}$ can be approximated with a factor of $O(\log d)^{d/2}$ in polynomial time. This problem also subsumes the problem of finding a simplex of largest volume in the convex hull of $n$ points in $Q^d$ for which we obtain the same approximation guarantee. The previously best known approximation guarantee for both problems was $d^{(d-1)/2}$ by Khachiyan. We further show that it is NP-hard to approximate both problems with a factor of~$c^d$ for some explicit constant~$c$. We highlight the importance of sub-determinants in combinatorial optimization by showing their significance in two problems. First, the Stable Set problem asks for a maximum cardinality set of pairwise non-adjacent vertices. The problem is NP-hard to approximate with factor $n^{1-\epsilon}$ for any $\epsilon>0$, where $n$ is the number of vertices. We restrict to instances where the sub-determinants of the constraint matrix are bounded by a function in~$n$. This is equivalent to restricting to graphs with bounded odd cycle packing number $ocp$, the maximum number of vertex-disjoint odd cycles in the graph. We obtain a polynomial-time approximation scheme for graphs with $ocp=o(n/\log n)$. Further, we obtain an $\alpha$-approximation algorithm for general graphs where~$\alpha$ smoothly increases from a constant to $n$ as $ocp$ grows from $O(n/\log n)$ to $n/3$. In contrast, we show that assuming the exponential-time hypothesis, Stable Set cannot be solved in polynomial time if $ocp=\Omega(\log^{1+\epsilon} n)$ for some $\epsilon>0$. Second, we consider coloring $n$ intervals with $k$ colors such that at each point on the line, the maximal difference between the number of intervals of any two colors is at most one. This problem induces a totally unimodular constraint matrix and is therefore efficiently solvable. We construct a fast algorithm with running time $O(n \log n + kn\log k)$.