A Coordinatewise Domain Scaling Algorithm for M-convex Function Minimization

1. Cunningham, W. H. and Frank, A.: A Primal-dual Algorithm for Submodular Flows. Math. Oper. Res. 10 (1985) 251–262

   Article  MathSciNet  MATH  Google Scholar 

2. Danilov, V., Koshevoy, G., Murota, K.: Discrete Convexity and Equilibria in Economies with Indivisible Goods and Money. Math. Social Sci. 41 (2001) 251–273

   Article  MathSciNet  MATH  Google Scholar 

3. Dress, A. W. M., Wenzel, W.: Valuated Matroid: A New Look at the Greedy Algorithm. Appl. Math. Lett. 3 (1990) 33–35

   Article  MathSciNet  MATH  Google Scholar 

4. Dress, A. W. M., Wenzel, W.: Valuated Matroids. Adv. Math. 93 (1992) 214–250

   Article  MathSciNet  MATH  Google Scholar 

5. Edmonds, J.: Submodular Functions, Matroids and Certain Polyhedra. In: Guy, R., Hanani, H., Sauer, N., Schönheim, J. (eds.): Combinatorial Structures and Their Applications. Gordon and Breach, New York (1970) 69–87

   Google Scholar 

6. Edmonds, J., Giles, R.: A Min-max Relation for Submodular Functions on Graphs. Ann. Discrete Math. 1 (1977) 185–204

   Article  MathSciNet  Google Scholar 

7. Frank, A.: Generalized Polymatroids. In: Hajnal, A., Lovász, L., Sós, V. T. (eds.): Finite and Infinite Sets, I. North-Holland, Amsterdam (1984) 285–294

   Google Scholar 

8. Frank, A., Tardos, É.: Generalized Polymatroids and Submodular Flows. Math. Program. 42 (1988) 489–563

   Article  MathSciNet  MATH  Google Scholar 

9. Fujishige, S.: Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector. Math. Oper. Res. 5 (1980) 186–196

   Article  MathSciNet  MATH  Google Scholar 

10. Fujishige, S.: Submodular Functions and Optimization. Annals of Discrete Mathematics 47, North-Holland, Amsterdam (1991)

    Google Scholar 

11. Groenevelt, H.: Two Algorithms for Maximizing a Separable Concave Function over a Polymatroid Feasible Region. European J. Oper. Res. 54 (1991) 227–236

    Article  MATH  Google Scholar 

12. Hochbaum, D. S.: Lower and Upper Bounds for the Allocation Problem and Other Nonlinear Optimization Problems. Math. Oper. Res. 19 (1994) 390–409

    Article  MathSciNet  MATH  Google Scholar 

13. Iwata, S.: A Fully Combinatorial Algorithm for Submodular Function Minimization. J. Combin. Theory Ser. B (to appear)

    Google Scholar 

14. Iwata, S., Shigeno, M.: Conjugate Scaling Algorithm for Fenchel-type Duality in Discrete Convex Optimization. SIAM J. Optim. (to appear)

    Google Scholar 

15. Iwata, S., Fleischer, L., Fujishige, S.: A Combinatorial Strongly Polynomial Algorithm for Minimizing Submodular Functions. J. ACM 48 (2001) 761–777

    Article  MathSciNet  MATH  Google Scholar 

16. Lovász, L.: Submodular Functions and Convexity. In: Bachem, A., Grötschel, M., Korte, B. (eds.): Mathematical Programming — The State of the Art. Springer-Verlag, Berlin (1983) 235–257

    Chapter  Google Scholar 

17. Moriguchi, S., Murota, K., Shioura, A.: Minimization of an M-convex Function with a Scaling Technique (in Japanese). IPSJ SIG Notes 2001-AL-76 (2001) 27–34

    Google Scholar 

18. Moriguchi, S., Murota, K., Shioura, A.: Scaling Algorithms for M-convex Function Minimization. IEICE Trans. Fund. (to appear)

    Google Scholar 

19. Murota, K.: Convexity and Steinitz’s Exchange Property. Adv. Math. 124 (1996) 272–311

    Article  MathSciNet  MATH  Google Scholar 

20. Murota, K.: Discrete Convex Analysis. Math. Program. 83 (1998) 313–371

    MathSciNet  MATH  Google Scholar 

21. Murota, K.: Submodular Flow Problem with a Nonseparable Cost Function. Combinatorica 19 (1999) 87–109

    Article  MathSciNet  MATH  Google Scholar 

22. Murota, K.: Matrices and Matroids for Systems Analysis. Springer-Verlag, Berlin (2000)

    MATH  Google Scholar 

23. Murota, K.: Discrete Convex Analysis (in Japanese). Kyoritsu Publ. Co., Tokyo (2001)

    Google Scholar 

24. Murota, K., Shioura, A.: Quasi M-convex and L-convex functions: Quasi-convexity in discrete optimization. Discrete Appl. Math. (to appear)

    Google Scholar 

25. Murota, K., Tamura, A.: New Characterizations of M-convex Functions and Their Applications to Economic Equilibrium Models with Indivisibilities. Discrete Appl. Math. (to appear)

    Google Scholar 

26. Murota, K., Tamura, A.: Application of M-convex Submodular Flow Problem to Mathematical Economics. In: Eades, P., Takaoka, T. (eds.): Proceedings of 12th International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, Vol. 2223. Springer-Verlag, Berlin Heidelberg New York (2001) 14–25

    Chapter  Google Scholar 

27. Rockafellar, R. T.: Convex Analysis. Princeton University Press, Princeton (1970)

    MATH  Google Scholar 

28. Schrijver, A.: A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time. J. Combin. Theory Ser. B 80 (2000) 346–355

    Article  MathSciNet  MATH  Google Scholar 

29. Shioura, A.: Minimization of an M-convex Function. Discrete Appl. Math. 84 (1998) 215–220

    Article  MathSciNet  MATH  Google Scholar 

Download references