 | |
Evaluierung und Weiterentwicklung des parametrischen Ansatzes für
algorithmische Graphenprobleme aus der Praxis
In den letzten Jahren wurde ein neuer, vielversprechender Ansatz
zur exakten Lösung von Problemen entwickelt, die in der
klassischen Komplexitätstheorie als schwer (zum Beispiel
NP-schwer) klassifiziert werden: parametrisierte Komplexität
Dieser von Fellows, Downey, Langston und vielen anderen entwickelte
Denkansatz ist
inzwischen komplexitätstheoretisch fundiert worden, und für viele
klassische NP-schwere Probleme konnte für meist
naheliegende Parametrisierungen der parametrisierte
Komplexitätsstatus bestimmt werden.
In diesem Projekt sollen systematisch Anwendungen
der parametrisierten Kompelxität auf Realweltprobleme untersucht werden.
Aus dieser Sichtweise stellt sich folgende grundlegende Aufgabe:
Gegeben ein algorithmische Problem, identifiziere einen oder mehrere geeignete Parameter, so dass
- diese Parameter typischerweise kleine Werte in der Praxis annehmen, und
- ein Algorithmus existiert, der effizient ist, sofern die Werte der
Parameter klein sind.
Diese Grundidee haben wir bisher erfolgreich an verschiedenen Realweltproblemen angewandt, die aus Kooperationen mit der Industrie stammen:
| Publikationen (sortiert nach Themenkreisen) |
- Durchsatzoptimierung bei der PC-Platinenbestückung
- M. Müller-Hannemann and K. Weihe
Moving Policies in Cyclic Assembly-Line Scheduling
Theoretical Computer Science, vol. 351, pp. 425-436, 2006.
Extended abstract appeared in Proceedings of the International Workshop on
Parameterized and Exact Computation (IWPEC 2004), Bergen, Norway,
Lecture Notes in Computer Science, vol. 3162, pp. 149-161, Springer.
- S. Tazari, M. Müller-Hannemann and K. Weihe
Workload Balancing in Multi-Stage Production Processes
WEA 2006, 5th Int. Workshop on Experimental Algorithms,
Lecture Notes in Computer Science 4007, pp. 49-60, Springer.
- Steinerbäume und Inverterbäume im VLSI
- M. Müller-Hannemann and A. Schulze
Approximation of Octilinear Steiner Trees Constrained
by Hard and Soft Obstacles
SWAT 2006, 10th Scandinavian Workshop on Algorithm Theory,
Lecture Notes in Computer Science 4059, pp. 242-254, Springer.
- M. Müller-Hannemann and Anna Schulze
Hardness and Approximation of Octilinear Steiner Trees
International Journal of Computational Geometry and Applications (IJCGA),
vol. 17, pp. 231-260, 2007.
Extended abstract in Proceedings of
The 16th Annual International Symposium on
Algorithms and Computation 2005 (ISAAC 2005),
Sanya, Hainan, China, Lecture Notes in Computer Science 3827, pp. 256-265, Springer, 2005.
- M. Müller-Hannemann and U. Zimmermann
Slack Optimization of Timing-Critical Nets,
11th Annual European Symposium on Algorithms (ESA 2003) ,
Lecture Notes in Computer Science, vol. 2832,
pp. 727-739, 2003.
- M. Müller-Hannemann and S. Peyer
Approximation of Rectilinear Steiner Trees with Length Restrictions on Obstacles,
8th Workshop on Algorithms and Data Structures (WADS 2003),
Carleton Univ., Ottawa, Canada, Lecture Notes in Computer Science, vol. 2748,
pp. 207-218, 2003
- Fahrplanauskunft im Fernverkehr
- M. Müller-Hannemann, F. Schulz, D. Wagner and C. Zaroliagis
Timetable Information: Models and Algorithms
LNCS Proceedings on
Algorithmic Methods for Railway Optimization, vol. 4359, pp. 67-89,
Springer, 2007.
- M. Müller-Hannemann and Karsten Weihe
On the Cardinality of the Pareto Set in Bicriteria Shortest Path
Problems
Annals of Operations Research, vol. 147, pp. 269-286, 2006.
- M. Müller-Hannemann and M. Schnee
Finding All Attractive Train Connections by Multi-Criteria
Pareto Search
Proceedings of the 4th Workshop on Algorithmic Methods
and Models for Optimization of Railways (ATMOS 2004), Bergen,
Norway, Lecture Notes in Computer Science, vol. 4359,
pp. 246-263, Springer, 2007.
- M. Müller-Hannemann and M. Schnee
Paying Less for Train Connections with MOTIS
ATMOS 2005, Palma de Mallorca, Spain.
- Just-in-Time Scheduling
- M. Müller-Hannemann and A. Sonnikow
Non-Approximability of Just-in-Time Scheduling
Technical Report, TU Darmstadt, Germany, 2006,
extended abstract in MAPSP 2007, Istanbul.
- Fast-planare Graphen
- Jan M. Hochstein and K. Weihe
Maximum s-t-flow with k Crossings in O(k^3 n log n) time
SODA 2007, Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Louisiana, USA, pages 843-847, 2007.
|
