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

Verbundforschung

Kalender

« Juni 2021 »
Mo Di Mi Do Fr Sa So
31 1 2
  • 12:00: KiNSIS-Kolloquium: Benchmarking, Prof. Dr. Malte Behrens, Anorganische Festkörperchemie
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
3 4 5 6
7 8
  • 16:15: Quantum carpets: A tool to observe decoherence (Prof. Dr. Wolfgang Schleich, University Ulm)
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
9
  • ganztägig: NanoTech Poland 2021
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
10
  • ganztägig: NanoTech Poland 2021
  • 16:00: Toward an objective assessment of mobility in clinical and daily activity assessments (Arash Atrsaei, EPFL)
  • Klicken Sie, um Details zu allen 2 Terminen zu sehen.
11
  • ganztägig: NanoTech Poland 2021
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
12 13
14 15 16 17
  • 17:00: Chemie in unterschiedlichen Dimensionen - von Molekülen über supramolekulare Aggregate zu optoelektronischen Bauteilen (Prof. Dr. Arne Lützen, Uni Bonn)
  • 17:00: "Chemie in unterschiedlichen Dimensionen - von Molekülen über supramolekulare Aggregate zu optoelektronischen Bauteilen" (Prof. Dr. Arne Lützen, Uni Bonn)
  • Klicken Sie, um Details zu allen 2 Terminen zu sehen.
18
  • 12:30: KiNSIS Transfer Lunch: Dr. Mindaugas Bulota, Head of National Innovation and Entrepreneurship Centre, Kaunas University of Technology (KTU), Lithuania „Technology transfer practices and success cases at KTU"
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
19 20
21 22
  • 16:15: The present and future of ESA's science program (Prof. Dr. Günther Hasinger, Director of Science, ESA)
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
23 24
  • 17:00: Leading beyond Chemistry: Research and Development at Evonik Industries AG (Dr. Felix Müller, Evonik Industries AG)
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
25 26 27
28 29
  • 16:15: Plasma 2020 – The US National Academies Decadal Assessment of Plasma Physics: Overview and Future Research Opportunities (Prof. Dr. Mark J. Kushner, University of Michigan)
  • Klicken Sie, um Details zu allen 1 Terminen zu sehen.
30 1 2 3 4