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

Aktuelle Pressemitteilungen

Medien

Veranstaltungen

Kalender

« November 2017 »
Mo Di Mi Do Fr Sa So
30 31 1 2
  • 19:30: Sternbilder – Sternsagen (Prof. Holger Kersten)
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
3 4
  • 12:00: Atome und Elektronen sehen? Tag der offenen Tür im DESY
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
5
6 7
  • 16:15: Microplasma arrays: Concept, configuration, characteristics and potential applications (Dr. Volker Schulz-von der Gathen, Bochum)
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
8
  • 20:00: Sternbilder – Sternsagen (Prof. Holger Kersten)
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
9
  • 17:00: tba, Prof. Dr. Stefan Jurga, Director of the NanoBioMedical Centre, Poznań, Poland
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
10 11
  • 10:15: Saturday Morning Physics
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
12
  • ganztägig: Saturday Morning Physics
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
13
  • ganztägig: Saturday Morning Physics
  • 17:15: tba. Prof. Elisabetta Chicca (Uni Bielefeld)
  • Klicken Sie, um Details zu allen 2 Terminen zu sehen.
14
  • ganztägig: Saturday Morning Physics
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
15
  • ganztägig: Saturday Morning Physics
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
16
  • ganztägig: Saturday Morning Physics
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
17
  • ganztägig: Saturday Morning Physics
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
18
  • ganztägig: Saturday Morning Physics
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
19
  • ganztägig: Saturday Morning Physics
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
20
  • ganztägig: Saturday Morning Physics
  • 17:15: Artificial Bandwidth Extension for Speech Signals Using Deep Neural Networks, M.Sc. Jonas Sauter, Nuance Communications
  • Klicken Sie, um Details zu allen 2 Terminen zu sehen.
21
  • ganztägig: Saturday Morning Physics
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
22
  • ganztägig: Saturday Morning Physics
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
23
  • ganztägig: Saturday Morning Physics
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
24
  • ganztägig: Saturday Morning Physics
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
25
  • ganztägig: Saturday Morning Physics
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
26
  • ganztägig: Saturday Morning Physics
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
27
  • ganztägig: Saturday Morning Physics
  • 17:15: Dr.-Ing. Vasudev Kanade Rajan
  • Klicken Sie, um Details zu allen 2 Terminen zu sehen.
28
  • ganztägig: Saturday Morning Physics
  • 15:00: Prof. Dr. Ulrich Stroth (TU München/IPP)
  • Klicken Sie, um Details zu allen 2 Terminen zu sehen.
29
  • ganztägig: Saturday Morning Physics
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
30
  • ganztägig: Saturday Morning Physics
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
1
  • ganztägig: Saturday Morning Physics
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
2
  • ganztägig: Saturday Morning Physics
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
3
  • ganztägig: Saturday Morning Physics
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.