**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# Node-weighted network design and maximum sub-determinants

Abstract

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)$.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Loading

Related publications

Loading

Related MOOCs

Loading

Related publications

Related MOOCs

No results

No results

Related concepts (7)

Approximation

An approximation is anything that is intentionally similar but not exactly equal to something else. The word approximation is derived from Latin approximatus, from proximus meaning very near and the prefix ad- (ad- before p becomes ap- by assimilation) meaning to. Words like approximate, approximately and approximation are used especially in technical or scientific contexts. In everyday English, words such as roughly or around are used with a similar meaning. It is often found abbreviated as approx.

Algorithm

In mathematics and computer science, an algorithm (ˈælɡərɪðəm) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can use conditionals to divert the code execution through various routes (referred to as automated decision-making) and deduce valid inferences (referred to as automated reasoning), achieving automation eventually.

Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.