| Beschreibung |
Diskrete Optimierung
Die diskrete / kombinatorische Optimierung ist ein Gebiet an der Schnittstelle von Mathematik und Informatik. Anwendungen für derartige Optimierungsprobleme sind in den vielfältigsten Bereichen zu finden.
Betrachtet werden sowohl diskrete Optimierungsprobleme, die effizient lösbar sind (kürzeste Wege, Flußprobleme), als auch NP-schwierige Probleme. Für letztere werden sowohl exakte Verfahren (Greedy-Algorithmen über Matroiden, Branch-and-Bound-Verfahren), als auch Heuristiken und Metaheuristiken zur näherungsweisen Lösung behandelt.
|
| engl. Beschreibung/ Kurzkommentar |
Discrete Optimization
Discrete / combinatorial optimization is an area at the borderline of mathematics and computer science. Applications for such optimization problems can be found in the most varied areas.
Consideration is given to discrete optimization problems, which are efficiently solvable (e.g. shortest paths, flow problems), as well as NP-hard problems. For the latter, both exact methods (greedy algorithms on matroids, branch-and-bound methods), as well as heuristics and metaheuristics, are introduced.
|
| Literatur |
J. Kleinberg, E. Tardos, Algorithm Design, Addison Wesley, 2005.
C. H. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Books on Computer Science, 2000 |
