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
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
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.