Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
|
locations | Term schedule | history
|
predoc-courses | schools | block-courses | workshops
partners


Monday Lecture and Colloquium


Monday, July 17, 2017

Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 041



Lecture - 14:15

Robert Weismantel - ETH Zurich

Parametrization of discrete optimization problems, subdeterminants and matrix-decomposition

Abstract:
The central goal of this talk is to identify parameters that explain the complexity of Integer linear programming defined as follows: Let P be a polyhedron. Determine an integral point in P that maximizes a linear function.

It is obvious that the number of integer variables is such a parameter. However, in view of applications in very high dimensions, the question emerges whether we need to treat all variables as integers? In other words, can we reparametrize integer programs with significantly less integer variables?

A second much less obvious parameter associated with an integer linear program is the number Delta defined as the maximum absolute value of any square submatrix of a given integral matrix A with m rows and n columns. This leads us to the important open question whether we can solve integer linear programming in a polynomial running time in Delta and the instance size?

Regarding the first question, we exhibit a variety of examples that demonstrate how integer programs can be reformulated using much less integer variables. To this end, we introduce a generalization of total unimodularity called the affine TU-dimension of a matrix and study related theory and algorithms for determining the affine TU-dimension of a matrix.

Regarding the second question, we present several new results that illustrate why Delta is an important parameter about the complexity of integer linear programs associated with a given matrix A. In particular, in the nondegenerate case integer linear programs with any constant value Delta can be solved in polynomial time. This extends earlier results of Veselov and Chirkov.




Colloquium - 16:00

Andreas Wiese - Universidad de Chile

Parameterized (1+eps)-approximation algorithms for packing problems

Abstract:
Approximation algorithms and parameterized algorithms are two well-established ways to deal with NP-hard problems. In the first case, the goal is to compute in polynomial time a solution of cost close to the optimum. In the second case, the goal is to compute an optimal solution in (FPT) time f(k)n^O(1), where k is some parameter of the input. The recent area of parameterized approximation seeks to combine the two approaches by, e.g., aiming for (1+eps)-approximations in f(k,eps)n^g(eps) time.

We present such algorithms for three important packing problems: for the Maximum Independent Set of Rectangles problem, for the Unsplittable Flow on a Path problem, and for the Two-Dimensional Knapsack problem with rotations. All three problems are W[1]-hard and hence we do not expect to find an FPT-algorithm for them. Also, it seems very difficult to construct a PTAS for them which motivates studying parameterized (1+eps)-approximations for them.



Letzte Aktualisierung: 29.06.2017