Algorithms and complexity results for submodular function maximization, traveling salesman and other graph design problems

• Algorithmen und Komplexitätsresultate für Maximierung submodularer Funktionen, das Traveling Salesman und andere Graph Design Probleme

Gottschalk, Corinna; Peis, Britta (Thesis advisor); Koster, Arie Marinus (Thesis advisor)

Aachen (2017)
Dissertation / PhD Thesis

Dissertation, RWTH Aachen University, 2017

Abstract

In combinatorial optimization, we distinguish between problems that can be solved in polynomial time and NP-hard problems for which no polynomial algorithm exists unless P = NP. Since many important problems with a wide range of applications fall into the second class, we are nevertheless interested in obtaining good solutions for NP-hard problems in polynomial time. To achieve this, we design approximation algorithms, which compute solutions whose values are provably close to the value of an optimal solution. An algorithm is an a-approximation if the ratio of any solution value and the optimal value is bounded above by a if it is a minimization problem and analogously for maximization problems. In this thesis, we are going to consider four problems, all of which are \NP-hard in general and analyze their behavior in terms of approximability. That means, our goals are finding approximation algorithms and bounds for the approximation ratio as well as understanding under which circumstances a problem can still be solved in polynomial time. First, we consider the s-t-path traveling salesman problem, a classical network design problem where the goal is to choose a minimum cost Hamiltonian s-t-path in a complete graph. We present a 1.566-approximation based on a new structural result that shows how to represent an LP solution as a convex combination of particular spanning trees. Next, we examine the minimum fractional additive stabilizer problem, where our goal is designing a stable graph from a given input graph by adding a minimum amount of edge weights. We show how to solve this problem on factor-critical graphs in polynomial time and use that to design an approximation algorithm for graphs where the Gallai-Edmonds decomposition has a special structure. Moreover, we show two strong results about hardness of approximation, which are the first super-constant hardness results for any graph stabilization problem. Then, we investigate a generalization of the network design problem to find a minimum cost spanning tree with k red edges in a graph whose edges are colored red and blue. This problem is well-understood on matroids and we generalize it to poset matroids, where the underlying structure is a partially ordered set instead of an unordered set. We analyze several special cases and present polynomial algorithms for some of them and strong hardness results for other variants. Finally, we consider submodular function maximization on distributive lattices. That is, the domains are given by the ideals on a partial order instead of all subsets of a set. We present several approximation algorithms, both for unconstrained maximization and for the case of additional side constraints induced by poset matroids.