A strongly polynomial time algorithm for a constrained submodular optimization problem (Q5951962)
From MaRDI portal
scientific article; zbMATH DE number 1687488
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A strongly polynomial time algorithm for a constrained submodular optimization problem |
scientific article; zbMATH DE number 1687488 |
Statements
A strongly polynomial time algorithm for a constrained submodular optimization problem (English)
0 references
2001
0 references
The author [Math. Oper. Res. 23, No. 3, 661--679 (1998; Zbl 0977.90073)] presented a weakly polynomial time algorithm for the problem of optimizing over the intersection of a submodular base polyhedron and an affine space (when the number of constraints describing the affine space is bounded). This paper contains a strongly polynomial time algorithm for this problem.
0 references
Submodular function
0 references
Base polyhedron
0 references
Max flow
0 references
Min cost spanning tree
0 references
