Timetable Combinatorial Optimization

Timetable Combinatorial Optimization

Sandro Bosio
IFOR, ETH-Zurich


DEI - Aula PT1
Monday June 11th, 2012
2.30 pm


Optimization problems involving time are widely studied in many areas of mathematics and control theory. However, relatively little is known about temporal counterparts of purely combinatorial problems, except for specific structures such as network flows and scheduling problems. In this talk we introduce a general setting for temporal extensions of combinatorial optimization problems.
Let a combinatorial problem P be given as a groundset A, with weights w_a for each element a in A, and a collection X of subsets of A. For example, let A be the edges of a graph, and X be its matchings. Given a time window W={1,...,T} and a duration t_a in W for each groundset element, we define a timetable solution as a collection of static solutions S_t in X , one for each time point t in W, such that a certain duration property is satisfied for all groundset elements. This property states that the time points at which an element a is selected must be partitionable into intervals of length t_a. Informally, whenever an element a is "activated", it must remain in the solution for exactly t_a time steps, after which it can be reactivated when desired.
Our main result for this problem class is an αβ-approximation algorithm, with α ≈ 1.691030, for the case in which X is an independence system and P admits a β-approximation algorithm. This algorithm considerably generalizes the α-approximation total- value heuristic by Kohli and Krishnamurti (1992) for integer knapsack, which can indeed be seen as the simplest version of a timetable problem.

Edoardo Amaldi

Research area:
Analisi applicata dei sistemi e ricerca operativa