000203533 001__ 203533 000203533 005__ 20181205220109.0 000203533 0247_ $$2doi$$a10.5075/epfl-thesis-6450 000203533 02470 $$2urn$$aurn:nbn:ch:bel-epfl-thesis6450-1 000203533 02471 $$2nebis$$a10278197 000203533 037__ $$aTHESIS 000203533 041__ $$aeng 000203533 088__ $$a6450 000203533 245__ $$aNode-weighted network design and maximum sub-determinants 000203533 269__ $$a2014 000203533 260__ $$aLausanne$$bEPFL$$c2014 000203533 336__ $$aTheses 000203533 502__ $$aProf. J. Pach (président) ; Prof. F. Eisenbrand (directeur) ; Prof. M. Di Summa, Prof. L. Sanità, Prof. O. N. A. Svensson (rapporteurs) 000203533 520__ $$aWe 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)$. 000203533 6531_ $$anode-weighted network design 000203533 6531_ $$asteiner forest 000203533 6531_ $$afeedback vertex set 000203533 6531_ $$aodd cycle packing 000203533 6531_ $$amaximum sub-determinant 000203533 6531_ $$amaximum volume simplex 000203533 6531_ $$aapproximation algorithms 000203533 700__ $$0245642$$aMoldenhauer, Carsten$$g213346 000203533 720_2 $$0240331$$aEisenbrand, Friedrich$$edir.$$g183121 000203533 8564_ $$s666388$$uhttps://infoscience.epfl.ch/record/203533/files/EPFL_TH6450.pdf$$yn/a$$zn/a 000203533 909C0 $$0252111$$pDISOPT$$xU11879 000203533 909CO $$ooai:infoscience.tind.io:203533$$pDOI$$pSB$$pthesis$$pthesis-bn2018$$qDOI2 000203533 917Z8 $$x108898 000203533 917Z8 $$x108898 000203533 917Z8 $$x108898 000203533 917Z8 $$x108898 000203533 917Z8 $$x108898 000203533 918__ $$aSB$$cMATHAA$$dEDMA 000203533 919__ $$aDISOPT 000203533 920__ $$a2014-11-24$$b2014 000203533 970__ $$a6450/THESES 000203533 973__ $$aEPFL$$sPUBLISHED 000203533 980__ $$aTHESIS