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.