{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,15]],"date-time":"2026-03-15T07:32:27Z","timestamp":1773559947400,"version":"3.50.1"},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"1-3","license":[{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1998,1]]},"DOI":"10.1007\/bf02680565","type":"journal-article","created":{"date-parts":[[2007,7,27]],"date-time":"2007-07-27T08:52:17Z","timestamp":1185526337000},"page":"313-371","source":"Crossref","is-referenced-by-count":157,"title":["Discrete convex analysis"],"prefix":"10.1007","volume":"83","author":[{"given":"Kazuo","family":"Murota","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"BF02680565_CR1","first-page":"551","volume-title":"Handbook of Combinatorics","author":"R.E. Bixby","year":"1995","unstructured":"R.E. Bixby, W.H. Cunningham, Matroid optimization and algorithms, in: R.L. Graham, M. Gr\u00f6tschel, L. Lov\u00e1sz (Eds.), Handbook of Combinatorics, vol. I, Chap. 11, Elsevier, Amsterdam, 1995, pp. 551\u2013609."},{"key":"BF02680565_CR2","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1137\/S0895480191222926","volume":"8","author":"A. Bouchet","year":"1995","unstructured":"A. Bouchet, W.H. Cunningham, Delta-matroids, jump systems and bisubmodular polyhedra, SIAM J. Discrete Math. 8 (1995) 17\u201332.","journal-title":"SIAM J. Discrete Math."},{"key":"BF02680565_CR3","volume-title":"Linear Programming","author":"V. Chv\u00e1tal","year":"1983","unstructured":"V. Chv\u00e1tal, Linear Programming, Freeman, New York, 1983."},{"key":"BF02680565_CR4","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0893-9659(95)00070-7","volume":"8","author":"A.W.M. Dress","year":"1995","unstructured":"A.W.M. Dress, W. Terhalle, Well-layered maps\u2014A class of greedily optimizable set functions, Appl. Math. Lett. 8 (1995) 77\u201380.","journal-title":"Appl. Math. Lett."},{"key":"BF02680565_CR5","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0893-9659(95)00040-W","volume":"8","author":"A.W.M. Dress","year":"1995","unstructured":"A.W.M. Dress, W. Terhalle, Well-layered maps and the maximum-degreek\u00d7k-subdeterminant of a matrix of rational functions, Appl. Math. Lett. 8 (1995) 19\u201323.","journal-title":"Appl. Math. Lett."},{"key":"BF02680565_CR6","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1006\/aama.1995.1022","volume":"16","author":"A.W.M. Dress","year":"1995","unstructured":"A.W.M. Dress, W. Tehalle, Rewarding maps\u2014On greedy optimization of set functions, Adv. in Appl. Math. 16 (1995) 464\u2013483.","journal-title":"Adv. in Appl. Math."},{"key":"BF02680565_CR7","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0893-9659(90)90009-Z","volume":"3","author":"A.W.M. Dress","year":"1990","unstructured":"A.W.M. Dress, W. Wenzel, Valuated matroid: A new look at the greedy algorithm, Appl. Math. Lett. 3 (1990) 33\u201335.","journal-title":"Appl. Math. Lett."},{"key":"BF02680565_CR8","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1016\/0001-8708(92)90028-J","volume":"93","author":"A.W.M. Dress","year":"1992","unstructured":"A.W.M. Dress, W. Wenzel, Valuated matroids, Adv. in Math. 93 (1992) 214\u2013250.","journal-title":"Adv. in Math."},{"key":"BF02680565_CR9","first-page":"69","volume-title":"Combinatorial Structures and Their Applications","author":"J. Edmonds","year":"1970","unstructured":"J. Edmonds, Submodular functions, matroids and certain polyhedra, in: R. Guy, H. Hanani, N. Sauer, J. Sch\u00f6nheim (Eds.), Combinatorial Structures and Their Applications, Gordon and Breach, New York, 1970, pp. 69\u201387."},{"key":"BF02680565_CR10","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0167-5060(08)70817-3","volume":"14","author":"J. Edmonds","year":"1979","unstructured":"J. Edmonds, Matroid intersection, Ann. Discrete Math. 14 (1979) 39\u201349.","journal-title":"Ann. Discrete Math."},{"key":"BF02680565_CR11","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1017\/CBO9781107325715.011","volume-title":"Combinatorial Geometries","author":"U. Faigle","year":"1987","unstructured":"U. Faigle, Matroids in combinatorial optimization, in: N. White (Ed.), Combinatorial Geometries, Cambridge University Press, London, 1987, pp. 161\u2013210."},{"key":"BF02680565_CR12","first-page":"3","volume":"53","author":"P. Favati","year":"1990","unstructured":"P. Favati, F. Tardella, Convexity in nonlinear integer programming, Ricerca Operativa 53 (1990) 3\u201344.","journal-title":"Ricerca Operativa"},{"key":"BF02680565_CR13","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1016\/0196-6774(81)90032-8","volume":"2","author":"A. Frank","year":"1981","unstructured":"A. Frank, A weighted matroid intersection algorithm, J. Algorithms 2 (1981) 328\u2013336.","journal-title":"J. Algorithms"},{"key":"BF02680565_CR14","first-page":"97","volume":"16","author":"A. Frank","year":"1982","unstructured":"A. Frank, An algorithm for submodular functions on graphs. Ann. Discrete Math. 16 (1982) 97\u2013120.","journal-title":"Ann. Discrete Math."},{"key":"BF02680565_CR15","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1007\/BF01589418","volume":"42","author":"A. Frank","year":"1988","unstructured":"A. Frank, E. Tardos, Generalized polymatroids and submodular flows, Math. Programming 42 (1988) 489\u2013563.","journal-title":"Math. Programming"},{"key":"BF02680565_CR16","first-page":"189","volume":"21","author":"S. Fujishige","year":"1978","unstructured":"S. Fujishige, Algorithms for solving the independent-flow problems, J. Oper. Res. Soc. Japan 21 (1978) 189\u2013204.","journal-title":"J. Oper. Res. Soc. Japan"},{"key":"BF02680565_CR17","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1007\/BF02592218","volume":"29","author":"S. Fujishige","year":"1984","unstructured":"S. Fujishige, Theory of submodular programs: A Fenchel-type min-max theorem and subgradients of submodular functions, Math. Programming 29 (1984) 142\u2013155.","journal-title":"Math. Programming"},{"key":"BF02680565_CR18","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1007\/BF02592001","volume":"29","author":"S. Fujishige","year":"1984","unstructured":"S. Fujishige, On the subdifferential of a submodular function, Math. Programming 29 (1984), 348\u2013360.","journal-title":"Math. Programming"},{"key":"BF02680565_CR19","volume-title":"Submodular Functions and Optimization, Annals of Discrete Mathematics","author":"S. Fujishige","year":"1991","unstructured":"S. Fujishige, Submodular Functions and Optimization, Annals of Discrete Mathematics, vol. 47, North-Holland, Amsterdam, 1991."},{"key":"BF02680565_CR20","unstructured":"S. Fujishige, K. Murota, On the relationship between L-convex functions and submodular integrally convex functions, RIMS Preprint 1152, Kyoto University, August 1997."},{"key":"BF02680565_CR21","unstructured":"S. Fujishige, K. Murota, Short proofs of the separation theorems for L-convex\/concave and M-convex\/concave functions, RIMS Preprint 1167, Kyoto University, October 1997."},{"key":"BF02680565_CR22","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1287\/moor.19.2.390","volume":"19","author":"D.S. Hochbaum","year":"1994","unstructured":"D.S. Hochbaum, Lower and upper bounds for the allocation problem and other nonlinear optimization problems, Math. Oper. Res. 19 (1994) 390\u2013409.","journal-title":"Math. Oper. Res."},{"key":"BF02680565_CR23","first-page":"269","volume":"69","author":"D.S. Hochbaum","year":"1995","unstructured":"D.S. Hochbaum, S.-P. Hong, About strongly polynomial time algorithms for quadratic optimization over submodular constraints, Math. Programming 69 (1995) 269\u2013309.","journal-title":"Math. Programming"},{"key":"BF02680565_CR24","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/BF01581207","volume":"55","author":"D.S. Hochbaum","year":"1992","unstructured":"D.S. Hochbaum, R. Shamir, J.G. Shanthikumar, A polynomial algorithm for an integer quadratic nonseparable transporation problem, Math. Programming 55 (1992) 359\u2013372.","journal-title":"Math. Programming"},{"key":"BF02680565_CR25","first-page":"32","volume":"19","author":"M. Iri","year":"1976","unstructured":"M. Iri, N. Tomizawa, An algorithm for finding an optimal \u2018independent assignment\u2019, J. Oper. Res. Soc. Japan 19 (1976) 32\u201357.","journal-title":"J. Oper. Res. Soc. Japan"},{"key":"BF02680565_CR26","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1016\/0022-247X(88)90421-0","volume":"133","author":"J. Kindler","year":"1988","unstructured":"J. Kindler, Sandwich theorems for set functions, J. Math. Anal. Appl. 133 (1988) 529\u2013542.","journal-title":"J. Math. Anal. Appl."},{"key":"BF02680565_CR27","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58191-5","volume-title":"Greedoids","author":"B. Korte","year":"1991","unstructured":"B. Korte, L. Lov\u00e1sz, R. Schrader, Greedoids, Springer, Berlin, 1991."},{"key":"BF02680565_CR28","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0012-365X(77)90118-2","volume":"19","author":"S. Krogdahl","year":"1977","unstructured":"S. Krogdahl, The dependence graph for bases in matroids. Discrete Math. 19 (1977) 47\u201359.","journal-title":"Discrete Math."},{"key":"BF02680565_CR29","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1017\/CBO9780511629563.007","volume-title":"Theory of Matroids","author":"J.P.S. Kung","year":"1986","unstructured":"J.P.S. Kung, Basis-exchange properties, in: N. White (Ed.), Theory of Matroids, Chap. 4, Cambridge University Press, London, 1986, pp. 62\u201375."},{"key":"BF02680565_CR30","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E.L. Lawler","year":"1976","unstructured":"E.L. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York, 1976."},{"key":"BF02680565_CR31","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/978-3-642-68874-4_10","volume-title":"Mathematical Programming\u2014The State of the Art","author":"L. Lov\u00e1sz","year":"1983","unstructured":"L. Lov\u00e1sz, Submodular functions and convexity, in: A. Bachem, M. Gr\u00f6tschel, B. Korte (Eds.), Mathematical Programming\u2014The State of the Art, Springer, Berlin, 1983, pp. 235\u2013257."},{"key":"BF02680565_CR32","first-page":"237","volume":"26","author":"M. Minoux","year":"1986","unstructured":"M. Minoux, Solving integer minimum cost flows with separable convex objective polynomially, Math. Programming 26 (1986), 237\u2013239.","journal-title":"Math. Programming"},{"key":"BF02680565_CR33","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0893-9659(95)00043-P","volume":"8","author":"K. Murota","year":"1995","unstructured":"K. Murota, Finding optimal minors of valuated bimatroids, Appl. Math. Lett. 8 (1995) 37\u201342.","journal-title":"Appl. Math. Lett."},{"key":"BF02680565_CR34","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1137\/S0895480195279994","volume":"9","author":"K. Murota","year":"1996","unstructured":"K. Murota, Valuated matroid intersection, I: Optimality criteria, SIAM J. Discrete Math. 9 (1996) 545\u2013561.","journal-title":"SIAM J. Discrete Math."},{"key":"BF02680565_CR35","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1137\/S0895480195280009","volume":"9","author":"K. Murota","year":"1996","unstructured":"K. Murota, Valuated matroid intersection, II: Algorithms, SIAM J. Discrete Math. 9 (1996) 562\u2013576.","journal-title":"SIAM J. Discrete Math."},{"key":"BF02680565_CR36","first-page":"357","volume":"82","author":"K. Murota","year":"1998","unstructured":"K. Murota, Fenchel-type duality for matroid valuations, Math. Programming 82 (1998) 357\u2013375.","journal-title":"Math. Programming"},{"key":"BF02680565_CR37","unstructured":"K. Murota, Submodular flow problem with a nonseparable cost function, Report No. 95843-OR, Forschungsinstitut f\u00fcr Diskrete Mathematik, Universit\u00e4t Bonn, 1995."},{"key":"BF02680565_CR38","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1006\/aima.1996.0084","volume":"124","author":"K. Murota","year":"1996","unstructured":"K. Murota, Convexity and Steinitz's exchange property, Adv. in Math. 124 (1996) 272\u2013311.","journal-title":"Adv. in Math."},{"key":"BF02680565_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1007\/3-540-61310-2_20","volume-title":"Integer Programming and Combinatorial Optimization","author":"K. Murota","year":"1996","unstructured":"K. Murota, Convexity and Steinitz's exchange property (Extended abstract), in: W. H. Cunningham, S.T. McCormick, M. Queyranne (Eds.), Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science 1084, Springer, Heidelberg, 1996, pp. 260\u2013274."},{"key":"BF02680565_CR40","unstructured":"K. Murota, A. Shioura, M-convex function on generalized polymatroid, Research Reports on Mathematical and Computing Sciences, Tokyo Institute of Technology, B-320, September 1996."},{"key":"BF02680565_CR41","volume-title":"Optimization, Handbooks in Operations Research and Management Science","year":"1989","unstructured":"G.L. Nemhauser, A.H.G. Rinnooy Kan, M.J. Todd (Eds.), Optimization, Handbooks in Operations Research and Management Science, vol. 1, Elsevier, Amsterdam, 1989."},{"key":"BF02680565_CR42","doi-asserted-by":"crossref","DOI":"10.1002\/9781118627372","volume-title":"Integer and Combinatorial Optimization","author":"G.L. Nemhauser","year":"1988","unstructured":"G.L. Nemhauser, L.A. Wolsey, Integer and Combinatorial Optimization, Wiley, New York, 1988."},{"key":"BF02680565_CR43","doi-asserted-by":"crossref","DOI":"10.1515\/9781400873173","volume-title":"Convex Analysis","author":"R.T. Rockafellar","year":"1970","unstructured":"R.T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ, 1970."},{"key":"BF02680565_CR44","volume-title":"SIAM Regional Conference Series in Applied Mathematics 16","author":"R.T. Rockafellar","year":"1974","unstructured":"R.T. Rockafellar, Conjugate duality and optimization, in: SIAM Regional Conference Series in Applied Mathematics 16, SIAM, Philadelphia, 1974."},{"key":"BF02680565_CR45","volume-title":"Network Flows and Monotropic Optimization","author":"R.T. Rockafellar","year":"1984","unstructured":"R.T. Rockafellar, Network Flows and Monotropic Optimization, Wiley, New York, 1984."},{"key":"BF02680565_CR46","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/B978-0-12-566780-7.50025-8","volume-title":"Progress in Combinatorial Optimization","author":"A. Schrijver","year":"1984","unstructured":"A. Schrijver, Total dual integrality from directed graphs, crossing families, and sub- and supermodular functions, in: W.R. Pulleyblank (Ed.), Progress in Combinatorial Optimization, Academic Press, New York, 1984, pp. 315\u2013361."},{"key":"BF02680565_CR47","volume-title":"Theory of Linear and Integer Programming","author":"A. Schrijver","year":"1986","unstructured":"A. Schrijver, Theory of Linear and Integer Programming, Wiley, New York, 1986."},{"key":"BF02680565_CR48","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/S0166-218X(97)00140-6","volume":"84","author":"A. Shioura","year":"1998","unstructured":"A. Shioura, Minimization of an M-convex function, Discrete Appl. Math. 84 (1998) 215\u2013220.","journal-title":"Discrete Appl. Math."},{"key":"BF02680565_CR49","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-46216-0","volume-title":"Convexity and Optimization in Finite Dimensions I","author":"J. Stoer","year":"1970","unstructured":"J. Stoer, C. Witzgall, Convexity and Optimization in Finite Dimensions I, Springer, Berlin, 1970."},{"key":"BF02680565_CR50","unstructured":"N. Tomizawa, Theory of hyperspaces (I)\u2014Supermodular functions and generalization of concept of \u2018bases\u2019 [in Japanese], Papers of the Technical Group on Circuit and System Theory, Institute of Electronics and Communication Engineers of Japan, CAS80-72, 1980."},{"key":"BF02680565_CR51","first-page":"834","volume":"57A","author":"N. Tomizawa","year":"1974","unstructured":"N. Tomizawa, M. Iri, An algorithm for determining the rank of a triple matrix product AXB with application to the problem of discerning the existence of the unique solution in a network [in Japanese], Trans. Inst. Electr. Comm. Engin. Japan 57A (1974) 834\u2013841; English translation: Electronics and Communications in Japan, 57A (1974) 50\u201357.","journal-title":"Trans. Inst. Electr. Comm. Engin. Japan"},{"key":"BF02680565_CR52","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1287\/opre.26.2.305","volume":"26","author":"D.M. Topkis","year":"1978","unstructured":"D.M. Topkis, Minimizing a submodular function on a lattice, Oper. Res. 26 (1978) 305\u2013321.","journal-title":"Oper. Res."},{"key":"BF02680565_CR53","volume-title":"Matroid Theory","author":"D.J.A. Welsh","year":"1976","unstructured":"D.J.A. Welsh, Matroid Theory, Academic Press, London, 1976."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02680565.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02680565\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02680565","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T07:52:31Z","timestamp":1558338751000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02680565"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":53,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["BF02680565"],"URL":"https:\/\/doi.org\/10.1007\/bf02680565","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}