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, May 4, 2015

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



Lecture - 14:15

Leen Stougie - VU University Amsterdam

A decomposition theory for vertex enumeration of convex polyhedra

Abstract:
In the last years the vertex enumeration problem of polyhedra has seen a revival in the study of metabolic networks, which increased the demand for efficient vertex enumeration algorithms for high-dimensional polyhedra given by equalities and inequalities. The complexity of enumeration of vertices of polytopes (bounded polyhedral) is a famous open problem in discrete and computational geometry.

In this paper we do not solve this problem, but present a type of fixed parameter tractable result. We apply the concept of branch-decomposition to the vertex enumeration problem of polyhedra P = {x : Sx = b; x >= 0}. For that purpose, we introduce the concept of k- module and show how it relates to the separators of the linear matroid generated by the columns of S. This then translates structural properties of the matroidal branch-decomposition to the context of polyhedra. We then use this to present a total polynomial time algorithm for polytopes P for which the branch-width of the linear matroid generated by S is bounded by a constant k.

This paper is joint work with Arne Reimers.




Colloquium - 16:00

Lin Chen - TU Berlin

An O(m2 log m)-Competitive Algorithm for Online Machine Minimization

Abstract:
We consider the online machine minimization problem in which jobs with hard deadlines arrive online over time at their release dates. The task is to determine a feasible schedule on a minimum number of machines. Our main result is a general O(m^2log m)-competitive algorithm for the preemptive online problem, where m is the optimal number of machines used in an offline solution. This is the first improvement on an O(log (p_{max}/p_{min}))-competitive algorithm by Phillips et al. (STOC 1997).

Our algorithm is constant-competitive if the offline optimum m is bounded by a constant. To develop the algorithm, we investigate two complementary special cases of the problem, namely, laminar instances and agreeable instances, for which we provide an O(log m)-competitive and an O(1)-competitive algorithm, respectively. Our O(1)-competitive algorithm for agreeable instances actually produces a non-preemptive schedule, which is of its own interest as there exists a strong lower bound of n for the general non-preemptive online machine minimization problem by Saha (FSTTCS 2013), which even holds for laminar instances. (Joint work with Kevin Schewior and Nicole Megow).



Letzte Aktualisierung: 28.04.2015