Kiel Nano, Surface and Interface Science (KiNSIS)

Kolloquiumsvortrag: Dr. Lin Chen

09.05.2014 von 14:15 bis 15:30

Kiel, Ludewig-Meyn-Str. 2, Übungsraum 2

Titel: "On the optimality of approximation schemes for the classical scheduling problem"
 
Abstract:
We consider the classical scheduling problem on parallel identical machines to minimize the makespan, and achieve the following results under the Exponential Time Hypothesis (ETH).

The scheduling problem on a constant number m of identical machines, denoted as Pm||Cmax , is known to admit an FPTAS of running time O(n)+(1/ϵ)O(m) . We prove it is essentially the best possible in the sense that a (1/ϵ)O(m1−δ)+nO(1) time FPTAS for any δ>0 implies that ETH fails.
The scheduling problem on an arbitrary number of identical machines, denoted as P||Cmax , is known to admit a PTAS of running time 2O(1/ϵ2log3(1/ϵ))+nO(1) . We prove it is nearly optimal in the sense that a 2O((1/ϵ)1−δ)+nO(1) time PTAS for any δ>0 implies that ETH fails.

We also obain lower bounds of exact algorithms for the scheduling problem that almost matches upper bounds.
This is joint work with K. Jansen and G. Zhang.

http://www.tf.uni-kiel.de/de/das-dekanat/aktuelles-termine/kolloquien/kolloquien-ss-2014/

Claudia Martin, 0431/880-6068

Diesen Termin meinem iCal-Kalender hinzufügen

zurück

Pressemitteilungen

Aktuelles

Veranstaltungen

Kalender

« Oktober 2018 »
Mo Di Mi Do Fr Sa So
1 2 3 4 5 6 7
8 9 10
  • 19:30: Können wir unser Oberstübchen nachbauen? Prof. Dr. Hermann Kohlstedt
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
11 12 13 14
15 16 17
  • 19:30: Psychoaktive Pflanzen, Pilze und Tiere, Prof. Dr. Christian Peifer
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
18 19 20 21
22
  • 17:15: Hybrid Spintronic-CMOS Microsystems - From Wearables to Implantables (Dr. Hadi Heidari, University of Glasgow)
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
23
  • ganztägig: Magie moderner Materialien: Von Flexiblen Keramiken und schwarzer Luft (Prof. Dr. Rainer Adelung)
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
24 25
  • 17:00: Selectivity Control in C-H Activation (Prof. Dr. Lutz Ackermann, Georg-August-Universität Göttingen)
  • 19:00: Die Physik des Bumerangs (Prof. Dr. Dietmar Block)
  • 19:30: Unsere kosmische Heimat (Prof. Dr. Sebastian Wolf)
  • Klicken Sie, um Details zu allen 3 Terminen zu sehen.
26 27 28
29
  • 17:15: From Constellation Shaping to Nonlinear Fourier Transform – On the Way to the Limits of Optical Data Links!? (Dr. Henning Bülow, Nokia Bell Labs Stuttgart)
  • 19:30: Max Planck und die Welt der Quanten (Prof. Dr. Michael Bonitz)
  • Klicken Sie, um Details zu allen 2 Terminen zu sehen.
30 31 1
  • 17:00: Computational-guided Discovery of MOFs towards energy and environmental-related applications (Prof. Guillaume Maurin, Université Montpellier & Institut Universitaire de Franc)
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
2 3 4