BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:Scheduling moldable monotone jobs [Oberseminar Discrete Optimizati
 on]
DTSTART:20241211T171500Z
DTEND:20241211T181500Z
DTSTAMP:20260721T194800Z
UID:indico-event-144@math-events.uni-bonn.de
DESCRIPTION:Speakers: Klaus Jansen (University of Kiel)\n\nA moldable job 
 is a job that can be executed on an arbitrary number of processors\, and w
 hose processing time depends on the number of processors allotted to it.\n
  A moldable job is monotone if its work doesn't decrease for an increasin
 g number of allotted processors. We consider the problem of scheduling mon
 otone moldable jobs to minimize the makespan. We argue that for certain co
 mpact input encodings a polynomial algorithm has a running time polynomial
  in n and log m\, where n is the number of jobs and m is the number of mac
 hines. We describe how monotony of jobs can be used to counteract the incr
 eased problem complexity that arises from compact encodings\, and give tig
 ht bounds on the approximability of the problem with compact encoding: it 
 is NP-hard to solve optimally\, but admits a PTAS. The main focus of this 
 work are efficient approximation algorithms. We describe different techniq
 ues to exploit the monotony of the jobs for better running times\, and pre
 sent a (3/2 + epsilon)-approximate algorithm whose running time is polynom
 ial in log m and 1/epsilon and only linear in the number n of jobs.\nThis 
 is joint work with my students Kilian Grage\, Felix Land and Felix Ohnesor
 ge.\nThe Oberseminar takes place in the Seminarraum\, 1st floor. Participa
 nts are invited to have coffee or tea in the lounge before.\n\nhttps://mat
 h-events.uni-bonn.de/event/144/
LOCATION:Arithmeum\, Lennéstr.\,  2 - Seminarraum (Arithmeum / Research I
 nstitute for Discrete Mathematics)
URL:https://math-events.uni-bonn.de/event/144/
END:VEVENT
END:VCALENDAR