 |
Combinatorial Algorithms
It is presumed that problems that are shown NP-complete cannot be
solved in polynomial time. Nevertheles, solutions to these problems
must be found, even if they are not optimal, as long as they can be
generated quickly. Besides devising such fast approximation algorithms
for combinatorial optimization problems, a considerable art is to
determine the quality of the obtained solution in terms of the optimum
solution without knowing it. Another important aspect of an
approximation algorithm is to present a bad input, a so-called
witness, that is an input where the algorithm may output quite a bad
feasible solution that is far away from the optimum
solution. Especially in the field of the Traveling Salesperson Problem
there are some heuristics in use where the gap between witnesses and
performance guarantees are still considerably large. In this focus
of research,
we would like to design good witnesses against some of these
heuristics.
Textbook
Publications
- Hoffmann, M.; Mühlenthaler, M.; Helwig, S.; Wanka, R.:
Discrete Particle Swarm Optimization for TSP:
Theoretical Results and Experimental
Evaluations;
in: Proc. International Conference on Adaptive and
Intelligent Systems (ICAIS); pp. 416-427, 2011.
(More
Information)
[doi:10.1007/978-3-642-23857-4_40]
- Mühlenthaler, M. ; Wanka, R.:
A Novel Event Insertion Heuristic for Finding Feasible
Solutions of Course Timetabling Problems;
in: Proc. 8th Int. Conf. on the Practice and Theory
of Automated Timetabling (PATAT)
2010, pp. 294-304.
(More Information)
- Helwig, S.; Hüffner, F.; Rössling, I.; Weinard, M.:
Selected Design Issues;
in: Algorithm Engineering - Bridging the Gap between
Algorithm Theory and Practice, Springer,
2010, pp. 58-126.
[doi:10.1007/978-3-642-14866-8_3]
Finished Theses
- Thomas Fersch.
Probabilistische Analyse von Einfügeheuristiken
für das Euklidische TSP.
Diplomarbeit, Lehrstuhl für Informatik 12,
Universität Erlangen-Nürnberg, April 2012.
- Daniel Zink.
Partikelschwarmoptimierung für das
Graphfärbungsproblem.
Bachelor-Arbeit, Lehrstuhl für Informatik 12,
Universität Erlangen-Nürnberg, März 2012.
- Andreas Fischer.
Partikelschwarmoptimierung für das
Set Cover Problem.
Bachelor-Arbeit, Lehrstuhl für Informatik 12,
Universität Erlangen-Nürnberg, September 2011.
- Florian Forster.
Evolutionäre Optimierung von Sortiernetzwerken.
Diplomarbeit, Lehrstuhl für Informatik 12,
Universität Erlangen-Nürnberg, Juli 2011.
- Lan Shi.
Approximation von Maxweight k-partite Matching für das
Nurse Rostering Problem.
Diplomarbeit, Lehrstuhl für Informatik 12,
Universität Erlangen-Nürnberg, März 2011.
- Thomas Fersch.
Die Einfüge-Distanz als Hilfsmittel zur Analyse
von Einfüge-Heuristiken für das
metrische Traveling Salesperson Problem.
Studienarbeit, Lehrstuhl für Informatik 12,
Universität Erlangen-Nürnberg, Januar 2011.
- Gerhard Pfeiffer.
Experimentelle Untersuchungen von Zeugenkonstruktionen gegen
die Farthest-Insertion-Heuristik und von weiteren Verfahren
für das Rundreiseproblem.
Diplomarbeit, Lehrstuhl für Informatik 12,
Universität Erlangen-Nürnberg, Dezember 2010.
- Matthias Hoffmann.
Partikelschwarmoptimierung für das TSP.
Studienarbeit, Lehrstuhl für Informatik 12,
Universität Erlangen-Nürnberg, November 2010.
- Berthold Immanuel Schmitt.
Effiziente randomisierte Algorithmen für das
Erfüllbarkeitsproblem - Beschleunigung durch
Variableninvertierung
Diplomarbeit, Lehrstuhl für Informatik 12,
Universität Erlangen-Nürnberg, November 2010.
- Matthias Ring.
Über die Stabilität von Heuristiken für
das TSP.
Bachelorarbeit, Lehrstuhl für Informatik 12,
Universität Erlangen-Nürnberg, September 2010.
- Florian Forster.
Analytische und experimentelle Varianzanalyse randomisierter
Algorithmen für das MaxSAT-Problem.
Studienarbeit, Lehrstuhl für Informatik 12,
Universität Erlangen-Nürnberg, Januar 2008.
- Matthias Gleiß.
Prinzipien des Organic Computing bei der Gesichtserkennung.
Studienarbeit, Lehrstuhl für Informatik 12,
Universität Erlangen-Nürnberg, Mai 2006.
|
|
