moteur de recherche

Séminaire Algo - Danny Hermelin
Séminaire Algo - Danny Hermelin
18-oct.-2016 14:30
Il y a: 2 yrs

Danny Hermelin

Loss minimization for geometric scheduling problems

Salle de séminaire (4B05R) - Bâtiment Copernic

In geometric scheduling, jobs are represented as geometric objects, and two jobs can be simultaneously scheduled together (on the same machine) if and only if their corresponding geometric objects do not intersect. The classical example in this area is interval scheduling where the intervals represent the timeline of each job, and two jobs can be simultaneously scheduled if and only if their timelines are disjoint. In loss minimization scheduling, our goal is to remove the minimum (weight or size) subset of jobs so that the remaining jobs can be scheduled together. Apart from the interval case, most loss minimization variants of geometric scheduling problems are NP-hard. In this talk I will present a generic framework for deriving efficient approximation algorithms for such problems, and exemplify this framework on three concrete examples.

<- retour: