*Wissenschaftliches Programm*   *Liste der Vortragenden*

Sektion 16
Dienstag, 19.09.2000, 16.00–16.20 Uhr, WIL C 307

Holographische Beweise und Approximierbarkeit von Mobilfunkproblemen

Heribert Vollmer, Universität Würzburg

Die Klasse NP wurde kürzlich charakterisiert mit Hilfe sogenannter probabilistisch-verifizierbarer Beweise. Diese Beweise sind so beschaffen, dass Mitgliedschaft eines Wortes in einer NP-Menge überprüft werden kann, indem Stichproben an nur konstant vielen Stellen im Beweis angesehen werden.

Wir verwenden dieses Resultat, um die (Nicht-) Approximierbarkeit von Problemen aus dem Bereich der Planung zellularer Netzwerke zu untersuchen. Wir weisen nach, dass viele bei verschiedenen Netzwerkttypen (GSM, UMTS) auftretende Probleme nicht approximierbar sind. Für praktisch interessante Spezialfälle können jedoch effiziente Approximationsalgorithmen angegeben werden.