| [home] - [up] |
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
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).