A strongly polynomial time algorithm for a constrained submodular optimization problem
Copyright policy )A strongly polynomial time algorithm for a constrained submodular optimization problem
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.
- University of Notre Dame United States
- College of Business Administration Latvia
Combinatorial optimization, Analysis of algorithms and problem complexity, Applied Mathematics, Programming involving graphs or networks, Max flow, Min cost spanning tree, Base polyhedron, Discrete Mathematics and Combinatorics, Submodular function, Abstract computational complexity for mathematical programming problems
Combinatorial optimization, Analysis of algorithms and problem complexity, Applied Mathematics, Programming involving graphs or networks, Max flow, Min cost spanning tree, Base polyhedron, Discrete Mathematics and Combinatorics, Submodular function, Abstract computational complexity for mathematical programming problems
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).1 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!