000203533 001__ 203533
000203533 005__ 20190317000044.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$$pthesis-bn2018$$pDOI$$pSB$$pthesis$$qDOI2$$qGLOBAL_SET
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