[home] - [up]


Lectures and Colloquia during the semester



May 6, 2002

Freie Universität Berlin - Institut für Informatik
Takustraße 9
14195 Berlin
Room 005           - map -
Lecture - 14:15

Sue Whitesides - School of Computer Science, McGill U., Montreal

Fixed Parameter Tractability Results for Some Graph Layout Problems

Abstract: A major initiative for dealing with apparently intractable problems has been the "fixed parameter tractability" approach of Downey and Fellows. Roughly, the basic idea is to identify a parameter of the problem to be solved so that the parameter is small in instances of practical interest, and then to design algorithms whose running time is a polynomial in the problem size, multiplied by an arbitrary (exponential) function of the parameter size. Thus for sufficiently small parameters, one can hope to obtain useful algorithms for problems that are in general NP-hard. This talk will describe how we have applied basic techniques from Fixed Parameter Tractability to some graph layout problems, where NP-hard problems abound.


Colloquium - 16:00

Edoardo Amaldi -DEI, Politecnico di Milano

On a new class of capacitated facility location problems arising in UMTS network planning

Abstract: Base station location and configuration in UMTS networks cannot only rely on signal predictions but must also consider the traffic distribution, the signal quality requirements and the power control mechanism. Therefore the two-phase approach adopted for second generation cellular systems where the planning problem is subdivided into a coverage problem and a frequency assignment problem is no longer appropriate. We investigate discrete optimization models and algorithms aimed at supporting the decisions in the process of selecting the location and configuration of base stations. Our models capture at different levels of detail the signal quality requirements and the specific power control mechanism of the Wideband CDMA air interface. In this talk the focus is on the uplink (mobile to base station) direction. We show why the related models differ from standard capacitated location problems, we discuss computational complexity issues and present computational results obtained with randomized greedy and Tabu Search algorithms for small to large-size instances.

This is joint work with Antonio Capone and Federico Malucelli (DEI).


[home] - [up] - [top]