ISSN:
1436-6304
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Description / Table of Contents:
Zusammenfassung Wir geben einen Überblick über wichtige Teilbereiche der kombinatorischen Optimierung, so wie sie sich heute darstellen. Der Schwerpunkt liegt auf neueren theoretischen Ergebnissen, die sich für Anwendungen in der Praxis als nützlich erwiesen haben. Abschnitt 2 dient der Vorstellung einzelner Beispiele und der Erläuterung unserer Bezeichnungsweise. Zentrale Begriffe aus der Komplexitätstheorie wie etwa die eines einfachen oder schwierigen Problems sind Gegenstand von Abschnitt 3. Ausgehend von Matroid-, Matching- und Netzwerkflußproblemen beschreiben wir anschlie-ßend, auf welche Weise polynomial lösbare Verallgemeinerungen dieser Probleme erhalten und in eine allgemeine Theorie submodularer Funktionen eingeordnet werden können. Im ersten Teil eines Abschnittes über Polyedertheorie besprechen wir orientierte Matroide, mit deren Hilfe die Theorie der konvexen Polyeder in einem rein kombinatorischen Rahmen verallgemeinert werden kann. Der 2. Teil befaßt sich mit Beziehungen zwischen linearen Systemen und Kombinatorik, hier besonders mit ganzzahligen Polyedern. Struktur und Bewertung von heuristischen Verfahren sind Gegenstand von Abschnitt 6. Schließlich beschreiben wir Ansätze zur Lösung schwieriger Optimierungsprobleme, die sich bei der Anwendung auf spezielle Problemklassen als leistungsfähig erwiesen haben.
Notes:
Summary We survey important parts of the theory of combinatorial optimization as it is developed today. The emphasis lies on new theoretical results, which have proven useful in practical applications. In Sect. 2 we present some examples and explain our basic notation. The purpose of Sect. 3 is to introduce central concepts of complexity theory, in particular the notions of easy and hard problems. Starting from matroid, matching and network flow problems we describe how polynomially solvable generalizations of these can be obtained, taking account of the theory of submodular functions as a general framework. Oriented matroids as a suitable concept by which to generalize the theory of convex polyhedra in a purely combinatorial setting are discussed in the first part of a section on polyhedral theory. Part 2 is concerned with the relations between linear systems and combinatorics, in particular integer polyhedra. The structure and evaluation of heuristic algorithms is the subject of Sect. 6. Finally, we describe basic ideas for the solution of hard optimization problems as they have proven efficient for particular problem classes.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01721246
Permalink
