Monday, November 2, 2015
Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005
Lecture - 14:15
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
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.