| Beschreibung |
Discrete and combinatorial optimization is a field situated at the intersection of mathematics and computer science. Applications for such optimization problems are found in a wide variety of areas. The focus is on discrete optimization problems that often cannot be solved efficiently (e.g., NP-hard problems). The subject covers exact methods (such as linear programming and backtracking) as well as heuristics and metaheuristics. Furthermore, it examines how tree decompositions can be utilized to develop efficient algorithms. |
| 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 |
