1993 | OriginalPaper | Buchkapitel
Submodular Functions
verfasst von : Martin Grötschel, László Lovász, Alexander Schrijver
Erschienen in: Geometric Algorithms and Combinatorial Optimization
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The concept of a submodular function in discrete optimization appears to be in several respects analogous to that of a convex function in continuous optimization. In many combinatorial theorems and problems, submodularity is involved, in one form or another, and submodularity often plays an essential role in a proof or an algorithm. Moreover, analogous to the fast methods for convex function minimization, it turns out that submodular functions can also be minimized fast, viz. in polynomial time. However, the only method known for this is, as yet, the ellipsoid method.