WFAP'07 - Second Workshop on Frequency Assignment Problems in Wireless Networks

Sadek (Trebic), September 23 - 27, 2007

Organized by DIMATIA and ITI

The workshop continues the tradition started at the first workshop, held in Certosa di Pontignano (Siena), Italy in October 2005.

Scope

The field of frequency assignment problems is a intensively studied research area. The task is to assign radio frequencies to transmitters in wireless networks without causing interference. These problems are usually combinatorially hard and the chance to reach an optimal solution is behind the scope of today computational resources. On the other hand, depending on the topology of the network (GSM, ad-hoc sensor network, etc.), on the underlying technology (e.g. analog vs digital data) and other parameters of the problem, various strategies may be designeed to obtain a reasonable and applicable solution.

The interest for this class of problems has grown up in the last decade, because the rapid development of new wireless services. Like with all scarcely available resources, the cost of frequency-use provides the need for economic use of the available frequencies. Reuse of frequencies within a wireless communication network can offer considerable economies. However, reuse of frequencies may also lead to a loss of quality of communication links. The use of (almost) the same frequency for multiple wireless connections can cause an interference between the signals that is unacceptable. The frequency assignment problem balances the economies of reuse of frequencies and the loss of quality in the network.

There is considerable literature devoted to the study of the frequency assignment problems, following many different approaches, including graph theory and combinatorics, simulated annealing, genetic algorithms, tabu search, and neural networks.

This workshop is intended to cover contributions in all these areas. In particular, it aims at bringing together scientists, engineers and practitioners of the field in order to have a forum for sharing and exchanging their experiences, for discussing fundamental challenges, reporting state-of-the-art and in-progress research, identifying future perspectives, and exchanging ideas about ongoing research to keep up with the rapid evolution and increasing complexity of such systems.

Format of the Workshop

The workshop will be focused on problem solving, which will be presented during the problem session on Sunday evening. Every day there will be a certain amount of time reserved for discussing about fundamental challenges, future perspectives, and new ideas, allowing people from different research areas to communicate and interact.

In addition, three research survey taks will be presented during the workshop:

Jerrold Griggs: Minimum Span Real Number Graph Labellings with Separation Conditions
Andreas Eisenblaetter: Automatic Frequency Planning in GSM networks: How to replenish the spectrum
Jean-Sebastien Sereni: Griggs and Yeh's Conjecture and the Probabilistic Method

Presentations will cover one among the different aspects of the Frequency Assignment Problems, or present a possible approach to the solution within a particular model.

See also the detailed program of the workshop.

Copies of the abstracts of the presentations together with proposed problems will be distributed during the workshop.

Conference photo

The list of participants

The following researchers participated at the workshop:

Roman Cada
Andreas Eisenblaetter
Louis Esperet
Jiri Fiala
Peter Golovach
Jerrold Griggs
Jan van den Heuvel
Jan Hladky
Vit Jelinek
Eva Jelinkova
Sandi Klavzar
Daniel Kral
Jan Kratochvil
Bernard Lidicky
Jozef Miskuf
Pavel Nejedly
Jaroslav Nesetril
Viresh Patel
Daniel Paulusma
Martin Pergel
Rosella Petreschi
Jean-Sebastien Sereni
Martin Tancer
Zsolt Tuza
Martin Vatshelle
Tomas Vyskocil

Local and travel instructions

The venue of the workshop is a wineyard lodge close to the castle Sadek, otherwise far away from civilization. Sporting activities include hiking and mountain biking.

As the number of rooms & beds is quite limited, we would welcome if you would be willing to share a room, so we can invite more participants to the workshop.

It is worth to note tht close to the conference location are three UNESCO cultural heritage sites: renaissance town and castle Telc, medieval Jewish town Trebic and castle-garden area Lednice-Valtice.

A bus shuttle from Prague is arranged on Sunday afternoon to the conference place and on Thursday afternoon back. The departure in Sunday is at 3 p.m. from the front of the Hotel of Czech Catholic Charity (address: Machova 7, Prague). The arrival on Thursday will be approx at 4 p.m. at the same place.

For other inquiries contact organizers at fap07@kam.mff.cuni.cz

August 2007 Jan Kratochvil, Dan Kral, Jiri Fiala