Article ID: | iaor20051115 |
Country: | Germany |
Volume: | 99 |
Issue: | 3 |
Start Page Number: | 539 |
End Page Number: | 562 |
Publication Date: | Jan 2004 |
Journal: | Mathematical Programming |
Authors: | Murota Kazuo, Tamura A. |
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