[Mittagsseminar TI] Fwd: [i-prof] Einladung zur Verteidigung meiner Bachelorarbeit

[Wolfgang Mulzer <mulzer@inf.fu-berlin.de>]

Nächsten Dienstag.


-------- Forwarded Message --------
Subject: [i-prof] Einladung zur Verteidigung meiner Bachelorarbeit
Date: Mon, 17 Oct 2016 17:13:15 +0200
From: michaela.borzechowski <michaela.borzechowski@fu-berlin.de>
To: i-studi@inf.fu-berlin.de, i-profs@inf.fu-berlin.de

Sehr geehrte Damen und Herren,

hiermit möchte ich Sie herzlich zur Verteidigung meiner Bachelorarbeit
mit dem Titel „The complexity class Polynomial Local Search (PLS) and
PLS-complete problems“ einladen.

Die Verteidigung findet im Rahmen des Mittagsseminars der Arbeitsgruppe
Theoretische Informatik am Dienstag, den 25.10. um 12:00 Uhr s.t. im
Raum 055 in der Takustr. 9 statt. Gutachter der Arbeit sind Prof. Dr.
Wolfgang Mulzer und M.Sc. Yannik Stein. Der Vortrag wird auf englisch
gehalten.

Mit freundlichen Grüßen,
Michaela Borzechowski


Abstract:
The complexity classes P and NP are well known. However we are often
interested in the actual globally optimal solutions of some NP decision
problems. Local search is an attempt to approximate a hard to find
global optimum with a local optimum. The complexity class Polynomial
Local Search (PLS) was introduced to analyze the complexity of local
search algorithms, where it is verifiable in polynomial time, whether a
solution is a local optimum or not. One can PLS-reduce local search
problems to one another and establish PLS-completeness. This work
presents the basic definitions of the class PLS, its relation to other
complexity classes, PLS-reductions, PLS-completeness, as well as a list
of PLS-complete problems. The aim is to give a general overview of this
topic and make further proofs for PLS-completeness and further
investigations of the characteristics of the class PLS easier.

_______________________________________________
Automatischer Mailverteiler an Gruppe 'ml-i-prof-mi'.
Hinweise dazu siehe Hilfeseite:
https://www.mi.fu-berlin.de/w/Tec/AnkuendigungsVerteiler

Attachment: smime.p7s
Description: S/MIME Cryptographic Signature