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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Baldick, R.: Refined proximity and sensitivity results in linearly constrained convex separable integer programming. Linear Algebra Appl. 226/228, 389–407 (1995)
Cook, W., Gerards, A.M.H., Schrijver, A., Tardos, E.: Sensitivity theorems in integer linear programming. Math. Program. 34, 251–264 (1986)
Edmonds, J., Giles, R.: A min-max relation for submodular functions on graphs. Ann. Discrete Math. 1, 185–204 (1977)
Favati, P., Tardella, F.: Convexity in nonlinear integer programming. Ricerca Operativa 53, 3–44 (1990)
Fujishige, S.: Submodular Functions and Optimization. Annals of Discrete Mathematics 47, North-Holland, Amsterdam, 1991
Fujishige, S., Katoh, N., Ichimori, T.: The fair resource allocation problem with submodular constraints. Math. Oper. Res. 13, 164–173 (1988)
Fujishige, S., Murota, K.: Notes on L-/M-convex functions and the separation theorems. Math. Program. 88, 129–146 (2000)
Granot, F., Skorin-Kapov, J.: Some proximity and sensitivity results in quadratic integer programming. Math. Program. 47, 259–268 (1990)
Hochbaum, D.S.: Lower and upper bounds for the allocation problem and other nonlinear optimization problems. Math. Oper. Res. 19, 390–409 (1994)
Hochbaum, D.S., Shanthikumar, J.G.: Convex separable optimization is not much harder than linear optimization. J. Assoc. Comput. Mach. 37, 843–862 (1990)
Ibaraki, T., Katoh, N.: Resource Allocation Problems: Algorithmic Approaches. The MIT Press, Cambridge, 1988
Ibaraki, T., Katoh, N.: Resource Allocation Problems. In: Du D.-Z., Pardalos P. M. (eds), Handbook of Combinatorial Optimization (Vol. 2), pp. 159–260. Kluwer Academic Publishers, Boston, 1998
Iwata, S.: Oral presentation at Workshop on Matroids, Matching, and Extensions. University of Waterloo, December, 1999
Iwata, S.: A fully combinatorial algorithm for submodular function minimization. J. Combin. Theory Ser. B 84, 203–212 (2002)
Iwata, S., Fleischer, L., Fujishige, S.: A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. Assoc. Comput. Mach. 48, 761–777 (2001)
Iwata, S., Shigeno, M.: Conjugate scaling algorithm for Fenchel-type duality in discrete convex optimization. SIAM J. Optim. 13, 204–211 (2002)
Moriguchi, S., Murota, K., Shioura, A.: Scaling algorithms for M-convex function minimization. IEICE Trans. Fundamentals, E85-A, 922–929 (2002)
Moriguchi, S., Shioura, A.: On Hochbaum’s scaling algorithm for the general resource allocation problem. Research Report B-377, Tokyo Institute of Technology, 2002
Murota, K.: Convexity and Steinitz’s exchange property. Adv. Math. 124, 272–311 (1996)
Murota, K.: Discrete convex analysis. Math. Program. 83, 313–371 (1998)
Murota, K.: Submodular flow problem with a nonseparable cost function. Combinatorica 19, 87–109 (1999)
Murota, K.: Matrices and Matroids for Systems Analysis. Springer-Verlag, Berlin, 2000
Murota, K.: Discrete Convex Analysis. Society for Industrial and Applied Mathematics, Philadelphia, 2003
Murota, K., Shioura, A.: M-convex function on generalized polymatroid. Math. Oper. Res. 24, 95–105 (1999)
Murota, K., Shioura, A.: Relationship of M-/L-convex functions with discrete convex functions by Miller and by Favati–Tardella. Discrete Appl. Math. 115, 151–176 (2001)
Murota, K., Shioura, A.: Quasi M-convex and L-convex functions: Quasi-convexity in discrete optimization. Discrete Appl. Math. To appear
Murota, K., Tamura, A.: Proximity theorems of discrete convex functions. RIMS Preprint 1358, Kyoto University, 2002
Schrijver, A.: A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Combin. Theory Ser. B 80, 346–355 (2000)
Shioura, A.: Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem. Discrete Appl. Math. To appear
Tamura, A.: Coordinatewise domain scaling algorithm for M-convex function minimization. In: Cook W.J., Schulz A.S. (eds), Proceedings of the Ninth Conference on Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science Vol. 2337, pp. 21–35. Springer-Verlag, Berlin, 2002
Author information
Authors and Affiliations
Corresponding author
Additional information
Mathematics Subject Classification (2000): 90C27, 05B35
Rights and permissions
About this article
Cite this article
Murota, K., Tamura, A. Proximity theorems of discrete convex functions. Math. Program., Ser. A 99, 539–562 (2004). https://doi.org/10.1007/s10107-003-0466-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-003-0466-7