Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, October 25, 2016, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: May Szedlák
The problem of detecting and removing redundant constraints is fundamental in optimization. We focus on the case of linear programs (LPs), given by $d$ variables with $n$ inequality constraints. A constraint is called redundant, if after removing it, the LP still has the same feasible region. The currently fastest method to detect all redundancies is due to Clarkson: it solves $n$ linear programs, but each of them has at most $s$ constraints, where $s$ is the number of nonredundant constraints. We study the special case where every constraint has at most two variables with nonzero coefficients. This family, denoted by $LI(2)$, has some nice properties. Namely, as shown by Aspvall and Shiloach, given a variable $x_i$ and a value $\lambda$, we can test in time $O(nd)$ whether there is a feasible solution with $x_i = \lambda$. Hochbaum and Naor present an $O(d^2 n \log n)$ algorithm for solving the feasibility problem in $LI(2)$. Their technique makes use of the Fourier-Motzkin elimination method and the earlier mentioned result by Aspvall and Shiloach. We present a strongly polynomial algorithm that solves redundancy detection in time $O(n d^2 s \log s)$. It uses a modification of Clarkson's algorithm, together with a revised version of Hochbaum and Naor's technique. This is joint work with Komei Fukuda.
Automatic MiSe System Software Version 1.4803M | admin login