Proximity theorems of discrete convex functions |
| |
| Authors: | Kazuo?Murota Email author" target="_blank">Akihisa?TamuraEmail author |
| |
| Institution: | (1) Department of Mathematical Informatics, Graduate School of Information Science and Technology, University of Tokyo, Tokyo, 113-8656, Japan; and PRESTO, JST, Tokyo, Japan;(2) Research Institute for Mathematical Sciences, Kyoto University, Kyoto, 606-8502, Japan |
| |
| Abstract: | 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, L2-convex functions and M2-convex functions, that are relevant to the polymatroid intersection problem and the submodular flow problem.Mathematics Subject Classification (2000): 90C27, 05B35 |
| |
| Keywords: | discrete convex analysis optimality criteria proximity properties |
| 本文献已被 SpringerLink 等数据库收录！ |
|
