Submodular function minimization

• 成果类型: Article; Proceedings Paper
• 署名作者: Iwata, Satoru
• 署名单位: Kyoto University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-006-0084-2
• 发表日期: 2008
• 页码: 45-64
• 关键词: capacity scaling algorithm; min-max theorem; Combinatorial algorithm; detachments; systems; performance; matroids; graphs; PROOF; set

摘要

Submodular functions often arise in various fields of operations research including discrete optimization, game theory, queueing theory and information theory. In this survey paper, we give overview on the fundamental properties of submodular functions and recent algorithmic devolopments of their minimization.