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, November 2, 2015

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005



Lecture - 14:15

Arnau Padrol - Université Pierre et Marie Curie


Scribability problems for polytopes

Abstract:
I will present some problems about the existence of realizations of combinatorial polytopes under geometric constraints involving the position of their faces with respect to the ball. Some of these are classical, such as inscribability and circumscribability, and some are new, like the (i,j)-scribability problem, which asks for realizations where i-faces avoid the ball while j-faces cut the ball. Among other results, I will show that cyclic polytopes with many vertices are not (1,d-1)-scribable.

This is joint work with Hao Chen.



Colloquium - 16:00

Kevin Schewior - TU Berlin


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


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 preemptive schedule on a minimum number of machines. Our main result is a general O(log m)-competitive algorithm for the online problem, where m is the optimal number of machines used in an offline solution. This is the first improvement on an intriguing problem in nearly two decades. To date, the best known result is a O(log p_min/p_max)-competitive algorithm by Phillips et al. (STOC 1997) that depends on the ratio of maximum and minimum job sizes, p_max and p_min. Even for m = 2 no better algorithm was known. Our algorithm is in this case constant-competitive. When applied to laminar or agreeable instances, our algorithm achieves a competitive ratio of O(1) even independently of m. The following two key components lead to our new result. Firstly, we derive a new lower bound on the optimum value that relates the laxity and the number of jobs with intersecting time windows. Then, we design a new algorithm that is tailored to this lower bound and balances the delay of jobs by taking the number of currently running jobs into account.




Letzte Aktualisierung: 26.10.2015