Jana Tabea Cslovjecsek
An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n.Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed parameter tractable.One example are block-structured integer programs, which exhibits a (recursive) block structure: The problem decomposes into independent and efficiently solvable sub-problems, if a small number of rows or columns are deleted from the constraint matrix. Prominent examples are 2-stage stochastic integer programs, n-fold integer programs and their generalizations.Previously known algorithms for these problems were based on the augmentation framework, a variant of local search tailored to integer programming. We propose a different approach. We provide new proximity bounds, independent of the number of sub-problems, for both n-fold and 2-stage stochastic integer programming. Further, we show that the relaxation can be solved efficiently via an adaptation of a parametric search framework.We apply our techniques to n-fold and 2-stage integer programming, and integer programming with bounded primal or dual treedepth. For these cases, we obtain strongly polynomial algorithms, which are near-linear in the dimension of the problem. Moreover, unlike the augmentation algorithms, our approach is highly parallelizable.For the second part of this thesis, the focus is shifted to a different NP-hard problem, the maximum (weight) independent set problem. We consider intersection graphs of axis-parallel rectangles or segments, both in the weighted and unweighted case. Given a set of weighted axis-parallel rectangles or segments, the task is to find a subset of pairwise non-intersecting objects with the maximum possible total weight. For weighted rectangles, the best-known polynomial-time approximation algorithm achieves an approximation factor of O(log log (n)). In the unweighted setting, constant factor approximation algorithms are known. It remains open if there are also constant factor approximation algorithms for the weighted setting.We give a parameterized approximation algorithm for finding a maximum weight independent set of axis-parallel rectangles. Given a parameter k, and e>0, the algorithm finds a set of non-overlapping rectangles with weight at least (1-e) opt(k) in 2^O(k log(k/e)) n^O(1/e) time, where opt(k) is the maximum weight of a solution of cardinality at most k. Note that, our algorithm may return a solution consisting of more than k rectangles. To complement this, we also propose a parameterized approximation algorithm for the case of axis-parallel segments. Here the algorithm finds a solution with cardinality at most k and total weight at least (1-e)opt(k) in time 2^O(k^2 log(k/e)) n^O(1).Lastly, we provide a nearly tight bound on the independence number of axis-parallel segments. More precisely, we prove that for any triangle-free intersection graph of n axis-parallel segments in the plane, the independence number of this graph is at least n/4 + c sqrt(n), for an absolute constant c. We complement this with a construction of a graph in this class, with an independence number at most n/4 + d sqrt(n) for an absolute constant d.
EPFL2023
