1998年9月
A note on minimizing submodular functions
INFORMATION PROCESSING LETTERS
- ,
- 巻
- 67
- 号
- 5
- 開始ページ
- 239
- 終了ページ
- 244
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1016/S0020-0190(98)00114-8
- 出版者・発行元
- ELSEVIER SCIENCE BV
For a given submodular function f on a finite set V, we consider the problem of finding a nonempty and proper subset X of V that minimizes f(X). If the function f is symmetric, then the problem can be solved by a purely combinatorial algorithm due to Queyranne (1995). This note considers a slightly more general condition than symmetry, i.e., f(X) + f(Y) greater than or equal to f(X - Y) + f(Y - X) for all X, Y subset of or equal to V, and shows that a modification of Queyranne's algorithm solves the problem by using O(\V\(3)) calls to function value oracle. In this case, all minimal optimal solutions can also be obtained by using O(\V\(3)) calls to function value oracle. (C) 1998 Elsevier Science B.V. All rights reserved.
- リンク情報
-
- DOI
- https://doi.org/10.1016/S0020-0190(98)00114-8
- DBLP
- https://dblp.uni-trier.de/rec/journals/ipl/NagamochiI98
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000076346000004&DestApp=WOS_CPL
- URL
- http://dblp.uni-trier.de/db/journals/ipl/ipl67.html#journals/ipl/NagamochiI98
- ID情報
-
- DOI : 10.1016/S0020-0190(98)00114-8
- ISSN : 0020-0190
- DBLP ID : journals/ipl/NagamochiI98
- Web of Science ID : WOS:000076346000004