A Combinatorial, Strongly Polynomial-Time Algorithm for Minimizing Submodular Functions

Details A Combinatorial, Strongly Polynomial-Time Algorithm for Minimizing Submodular Functions A Combinatorial, Strongly Polynomial-Time Algorithm for Minimizing Submodular Functions

2000-04-13

arxiv.org/abs/math/0004089v1

Mathematics

Combinatorics

17 pages

Scientific paper

This paper presents the first combinatorial polynomial-time algorithm for minimizing submodular set functions, answering an open question posed in 1981 by Grotschel, Lovasz, and Schrijver. The algorithm employs a scaling scheme that uses a flow in the complete directed graph on the underlying set with each arc capacity equal to the scaled parameter. The resulting algorithm runs in time bounded by a polynomial in the size of the underlying set and the largest length of the function value. The paper also presents a strongly polynomial-time version that runs in time bounded by a polynomial in the size of the underlying set independent of the function value.

Affiliated with

Also associated with

No associations

Rating

A Combinatorial, Strongly Polynomial-Time Algorithm for Minimizing Submodular Functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Combinatorial, Strongly Polynomial-Time Algorithm for Minimizing Submodular Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Combinatorial, Strongly Polynomial-Time Algorithm for Minimizing Submodular Functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-573732