In:
Journal of the ACM, Association for Computing Machinery (ACM), Vol. 48, No. 4 ( 2001-07), p. 761-777
Abstract:
This paper presents a combinatorial polynomial-time algorithm for minimizing submodular functions, answering an open question posed in 1981 by Grötschel, Lovász, 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 length of the largest absolute function value. The paper also presents a strongly polynomial version in which the number of steps is bounded by a polynomial in the size of the underlying set, independent of the function values.
Type of Medium:
Online Resource
ISSN:
0004-5411
,
1557-735X
DOI:
10.1145/502090.502096
Language:
English
Publisher:
Association for Computing Machinery (ACM)
Publication Date:
2001
detail.hit.zdb_id:
2006500-0
detail.hit.zdb_id:
6759-3
Permalink