[Mittagsseminar TI] Fwd: [i-prof] Approximative Computations on Spanning Trees with Low Crossing Number: Verteidigung meiner Masterarbeit / Defense of my master thesis

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

-------- Original Message --------
Subject: [i-prof] Approximative Computations on Spanning Trees with Low
Crossing Number: Verteidigung meiner Masterarbeit / Defense of my master
thesis
Date: Wed, 24 Jul 2013 10:07:58 +0200
From: Maximilian Konzack <maximilian.konzack@fu-berlin.de>
To: i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de,
i-studi@inf.fu-berlin.de, renee.zentiks@fu-berlin.de

Sehr geehrte Damen und Herren,

auch ich will mein Studium beenden, deshalb lade ich Sie herzlich zur
Verteidigung meiner Masterarbeit ein.

Dear Sir or Madam,

I am pleased to invite you to the defense of my master thesis.

Datum / Date:
Dienstag/Tuesday, 30.07.13

Raum / Room:
SR 055 (Takustr. 9)

Zeit / Time:
12:00 Uhr (s.t.)

Betreuer / Supervisors:
Prof. Dr. Wolfgang Mulzer
Dr. Panos Giannopoulos

Zusammenfassung / Abstract:
On undirected and complete graphs having n points and a set of lines,
the crossing number is the maximum number of intersections with a line
for a spanning tree. Spanning Tree with Low Crossing Number (STLCN) is
an optimization problem to minimize the crossing number. The computation
of STLCN is assumed to be NP-hard. The aim of this study was to
investigate the current approximations for STLCN and to revise some of
their drawbacks. In this master thesis a new approximation was
established using connected components in LP solving. Another aim was to
evaluate the quality of the approximations on the crossing number in a
computation study. Therefore, a comprehensive Python library for STLCN
was developed. The experiments on most settings confirm a crossing
number of O(sqrt(n)) which is consistent with the theory proving the
existence of such a spanning tree. The proposed approximation compares
well with the others. The iterative reweighting method, an widely
applied meta method used for instance in the AdaBoost algorithm within
the field of machine learning, is able to compute spanning trees with
significantly fewer crossings. The evaluation of the computations
indicates that optimizing STLCN leads to an average crossing number of
O(log(n)). These results suggest that the crossing number may be
approximated more tightly than expected. Those experiments on STLCN were
applied ranging from artificial data sets to real data points from TSPLIB.

Mit freundlichen Grüßen, / Kind regards,
Maximilian Konzack

_______________________________________________
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