Proximity theorems of discrete convex functions

• 成果类型: Article
• 署名作者: Murota, K; Tamura, A
• 署名单位: University of Tokyo; Japan Science & Technology Agency (JST); Kyoto University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-003-0466-7
• 发表日期: 2004
• 页码: 539-562
• 关键词: minimizing submodular functions; Combinatorial algorithm; function minimization; allocation problem; optimization

摘要

A Proximity theorem is a statement that, given an optimization problem and its relaxation, an optimal solution to the original problem exists in a certain neighborhood of a solution to the relaxation. Proximity theorems have been used successfully, for example, in designing efficient algorithms for discrete resource allocation problems. After reviewing the recent results for L-convex and M-convex functions, this paper establishes Proximity theorems for larger classes of discrete convex functions, L-2-convex functions and M-convex functions. that are relevant to the polymatroid intersection problem and the submodular flow problem.