On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

Knapsack problems give a simple framework for decision making. A classical example is the min-knapsack problem (MinKnap): choose a subset of items with minimum total cost, whose total profit is above a given threshold. While this model successfully generalizes to problems in scheduling, network design and capacited location, its dynamic programming approaches do not. One often relies on strong polyhedral relaxations for corresponding integer programs instead. Among other results, we construct such a relaxation for the time-invariant incremental knapsack problem (IIK), and study classes of valid inequalities for MinKnap.

IIK is covered in the first part of this thesis. It is a generalization of the max-knapsack problem to a discrete multi-period setting. At each time, capacity increases and items can be added, but not removed from the knapsack. The goal is to maximize the sum of profits over all times. IIK models scenarios in specific financial markets and governmental decision processes. It is known to be strongly NP-hard and there has been work on approximation algorithms for special cases. We settle the complexity of IIK by designing a PTAS, and provide several extensions of the technique.

The second part is on MinKnap and divided into two chapters. One is motivated by a recent work on disjunctive relaxations for MinKnap with fixed objective function, where we reduce the size of the construction. The other focuses on a class of bounded pitch inequalities, that generalize the unweighted cover inequalities for MinKnap. While separating over pitch-1 inequalities is NP-hard, we show that approximate separation over the set of pitch-1 and pitch-2 inequalities can be done in polynomial time. We also investigate integrality gaps of linear relaxations for MinKnap when these inequalities are added. Consequently we show that, for any fixed t, the t-th CG closure of the natural relaxation has unbounded gap.

The last chapter deals with questions in clustered planarity testing. The Hanani-Tutte theorem is a classical result that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generalize this result to clustered graphs with two disjoint clusters, and show that a straightforward extension to flat clustered graphs with three or more disjoint clusters is not possible. For general clustered graphs we show a variant of the Hanani-Tutte theorem in the case when each cluster induces a connected subgraph. We conclude by a short proof, using matroid intersection, for a result by Di Battista and Frati on embedded clustered graphs.

New Graph Algorithms via Polyhedral Techniques

Jakub Tarnawski

In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. Somewhat surprisingly, similar polyhedral techniques can be harnessed in the two seemingly disparate settings. In the first part of the thesis we address a benchmark problem in combinatorial optimization: the asymmetric traveling salesman problem (ATSP). It consists in finding the shortest tour that visits all vertices of a given directed graph with weights on edges. Due to its NP-hardness, the theoretical study of algorithms for ATSP has focused on approximation algorithms: ones that are provably both efficient and give solutions competitive with the optimum. Specifically, a rho-approximation algorithm for ATSP is one that runs in polynomial time and always outputs a tour that is at most rho times longer than the shortest tour. Finding such an approximation algorithm with rho bounded (i.e., a constant factor) had been a long-standing open problem. In this thesis, we give such an algorithm. Our approximation guarantee is analyzed with respect to the standard linear programming relaxation, and thus our result also confirms the conjectured constant integrality gap of that relaxation. Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics due to Svensson. In particular, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. This reduction takes advantage of a laminar family of vertex sets that arises from the linear programming relaxation. In the second part of the thesis we address the perfect matching problem. The first polynomial-time algorithm for it, given by Edmonds in 1965, is historically associated with the introduction of the class P and our notion that polynomial-time'' means efficient''. That algorithm is sequential and deterministic. We have also known since the 1980s that the matching problem has efficient parallel algorithms if the use of randomness is allowed. Formally, it is in the class RNC, i.e., it has randomized algorithms that use polynomially many processors and run in polylogarithmic time. However, we do not know if randomness is necessary - that is, whether the matching problem is in the class NC. In this thesis we show that the matching problem is in quasi-NC. That is, we give a deterministic parallel algorithm that runs in O(log^3 n) time on n^{O(log^2 n)} processors. The result is obtained by a derandomization of the Isolation Lemma for perfect matchings, which was introduced in the classic paper by Mulmuley, Vazirani and Vazirani to obtain an RNC algorithm. Our proof extends the framework of Fenner, Gurjar and Thierauf, who proved the analogous result in the special case of bipartite graphs. Compared to that setting, several new ingredients are needed due to the significantly more complex structure of perfect matchings in general graphs. In particular, our proof heavily relies on the laminar structure of the faces of the perfect matching polytope.

EPFL2019

Node-weighted network design and maximum sub-determinants

Carsten Moldenhauer

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

ocp

grows from

O(n/\log n)

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)

EPFL2014