Proximity theorems of discrete convex functions

Proximity theorems of discrete convex functions

0.00 Avg rating0 Votes
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: ,
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.

Reviews

Required fields are marked *. Your email address will not be published.