{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:24:39Z","timestamp":1759638279806},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2014,7,2]],"date-time":"2014-07-02T00:00:00Z","timestamp":1404259200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2015,8]]},"DOI":"10.1007\/s10107-014-0792-y","type":"journal-article","created":{"date-parts":[[2014,7,1]],"date-time":"2014-07-01T18:36:14Z","timestamp":1404239774000},"page":"435-466","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["A framework of discrete DC programming by discrete convex analysis"],"prefix":"10.1007","volume":"152","author":[{"given":"Takanori","family":"Maehara","sequence":"first","affiliation":[]},{"given":"Kazuo","family":"Murota","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,7,2]]},"reference":[{"key":"792_CR1","doi-asserted-by":"crossref","first-page":"961","DOI":"10.1080\/02331931003770411","volume":"60","author":"M Ba\u010d\u00e1k","year":"2011","unstructured":"Ba\u010d\u00e1k, M., Borwein, J.M.: On difference convexity of locally Lipschitz functions. Optimization 60, 961\u2013978 (2011)","journal-title":"Optimization"},{"key":"792_CR2","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1215\/S0012-7094-37-00334-X","volume":"3","author":"G Birkhoff","year":"1937","unstructured":"Birkhoff, G.: Rings of sets. Duke Math. J. 3, 443\u2013454 (1937)","journal-title":"Duke Math. J."},{"key":"792_CR3","doi-asserted-by":"crossref","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G Calinescu","year":"2011","unstructured":"Calinescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. 40, 1740\u20131766 (2011)","journal-title":"SIAM J. Comput."},{"key":"792_CR4","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1016\/0001-8708(92)90028-J","volume":"93","author":"AWM Dress","year":"1992","unstructured":"Dress, A.W.M., Wenzel, W.: Valuated matroids. Adv. Math. 93, 214\u2013250 (1992)","journal-title":"Adv. Math."},{"key":"792_CR5","first-page":"69","volume-title":"Combinatorial Structures and Their Applications","author":"J Edmonds","year":"1970","unstructured":"Edmonds, J.: Submodular functions, matroids and certain polyhedra. In: Guy, R., Hanani, H., Sauer, N., Sch\u00f6nheim, J. (eds.) Combinatorial Structures and Their Applications, pp. 69\u201387. Gordon and Breach, New York (1970)"},{"key":"792_CR6","first-page":"3","volume":"53","author":"P Favati","year":"1990","unstructured":"Favati, P., Tardella, F.: Convexity in nonlinear integer programming. Ricerca Operat. 53, 3\u201344 (1990)","journal-title":"Ricerca Operat."},{"key":"792_CR7","doi-asserted-by":"crossref","first-page":"1133","DOI":"10.1137\/090779346","volume":"40","author":"U Feige","year":"2011","unstructured":"Feige, U., Mirrokni, V.S., Vondr\u00e1k, J.: Maximizing non-monotone submodular functions. SIAM J. Comput. 40, 1133\u20131153 (2011)","journal-title":"SIAM J. Comput."},{"key":"792_CR8","doi-asserted-by":"crossref","unstructured":"Frank, A.: Generalized polymatroids. In: Hajnal, A., Lov\u00e1sz, L., S\u00f3s, V. T. (eds.) Finite and Infinite Sets, (Proceedings of 6th Hungarian Combinatorial Colloquium, 1981), Colloquia Mathematica Societatis J\u00e1nos Bolyai, vol. 37, pp. 285\u2013294, North-Holland (1984)","DOI":"10.1016\/B978-0-444-86893-0.50021-8"},{"key":"792_CR9","unstructured":"Frank, A.: Connections in Combinatorial Optimization. Oxford Lecture Series in Mathematics and its Applications, 38, Oxford University Press, Oxford (2011)"},{"key":"792_CR10","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1007\/BF01589418","volume":"42","author":"A Frank","year":"1988","unstructured":"Frank, A., Tardos, \u00c9.: Generalized polymatroids and submodular flows. Math. Program. 42, 489\u2013563 (1988)","journal-title":"Math. Program."},{"key":"792_CR11","unstructured":"Fujishige, S.: Submodular Functions and Optimization, 2nd edn. Annals of Discrete Mathematics, vol. 58. Elsevier, Amsterdam (2005)"},{"key":"792_CR12","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/PL00011371","volume":"88","author":"S Fujishige","year":"2000","unstructured":"Fujishige, S., Murota, K.: Notes on L-\/M-convex functions and the separation theorems. Math. Program. 88, 129\u2013146 (2000)","journal-title":"Math. Program."},{"key":"792_CR13","doi-asserted-by":"crossref","first-page":"707","DOI":"10.2140\/pjm.1959.9.707","volume":"9","author":"P Hartman","year":"1959","unstructured":"Hartman, P.: On functions representable as a difference of convex functions. Pac. J. Math. 9, 707\u2013713 (1959)","journal-title":"Pac. J. Math."},{"key":"792_CR14","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1007\/BF03167590","volume":"21","author":"H Hirai","year":"2004","unstructured":"Hirai, H., Murota, K.: M-convex functions and tree metric. Jpn. J. Ind. Appl. Math. 21, 391\u2013403 (2004)","journal-title":"Jpn. J. Ind. Appl. Math."},{"key":"792_CR15","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/978-3-642-45610-7_3","volume":"256","author":"JB Hiriart-Urruty","year":"1985","unstructured":"Hiriart-Urruty, J.B.: Generalized differentiability, duality and optimization for problems dealing with differences of convex functions. Lecture Note Econ. Math. Syst. 256, 37\u201370 (1985)","journal-title":"Lecture Note Econ. Math. Syst."},{"key":"792_CR16","first-page":"219","volume-title":"Nonsmooth Optimization and Related Topics, Ettore Majorana International Sciences, Physical Sciences, Series 43","author":"JB Hiriart-Urruty","year":"1989","unstructured":"Hiriart-Urruty, J.B.: From convex optimization to nonconvex optimization, Part I: Necessary and sufficient conditions for global optimality. In: Clarke, F.H., Dem\u2019yanov, V.F., Giannessi, F. (eds.) Nonsmooth Optimization and Related Topics, Ettore Majorana International Sciences, Physical Sciences, Series 43, pp. 219\u2013239. Plenum Press, New York (1989)"},{"key":"792_CR17","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-02796-7","volume-title":"Convex Analysis and Minimization Algorithms I","author":"J-B Hiriart-Urruty","year":"1993","unstructured":"Hiriart-Urruty, J.-B., Lemar\u00e9chal, C.: Convex Analysis and Minimization Algorithms I. Springer, Berlin (1993)"},{"key":"792_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1023\/A:1021765131316","volume":"103","author":"R Horst","year":"1999","unstructured":"Horst, R., Thoai, N.V.: DC Programming: overview. J. Opt. Theory Appl. 103, 1\u201343 (1999)","journal-title":"J. Opt. Theory Appl."},{"key":"792_CR19","doi-asserted-by":"crossref","unstructured":"Iwata S., Orlin, J.B.: A simple combinatorial algorithm for submodular function minimization. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, pp. 1230\u20131237 (2009)","DOI":"10.1137\/1.9781611973068.133"},{"key":"792_CR20","unstructured":"Iyer, R., Bilmes, J.: Algorithms for approximate minimization of the difference between submodular functions, with applications. In: Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, pp. 407\u2013417. Also: http:\/\/arxiv.org\/abs\/1207.0560 (2012)"},{"key":"792_CR21","unstructured":"Iyer, R., Jegelka, S., Bilmes, J.: Fast semidifferential-based submodular function optimization. In: Proceedings of the 30th International Conference on Machine Learning, pp. 855\u2013863 (2013)"},{"key":"792_CR22","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/j.patrec.2010.08.008","volume":"32","author":"Y Kawahara","year":"2011","unstructured":"Kawahara, Y., Nagano, K., Okamoto, Y.: Submodular fractional programming for balanced clustering. Pattern Recogn. Lett. 32, 235\u2013243 (2011)","journal-title":"Pattern Recogn. Lett."},{"key":"792_CR23","unstructured":"Kawahara, Y., Washio, T.: Prismatic algorithm for discrete D.C. programming problem. In: Proceedings of the 25th Annual Conference on Neural Information Processing Systems, pp. 2106\u20132114 (2011)"},{"key":"792_CR24","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1016\/j.disopt.2009.04.006","volume":"6","author":"V Kolmogorov","year":"2009","unstructured":"Kolmogorov, V., Shioura, A.: New algorithms for convex cost tension problem with application to computer vision. Discret. Optim. 6, 378\u2013393 (2009)","journal-title":"Discret. Optim."},{"key":"792_CR25","doi-asserted-by":"crossref","unstructured":"Lee, J., Mirrokni, V.S., Nagarajan, V., Sviridenko, M.: Non-monotone submodular maximization under matroid and knapsack constraints. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pp. 323\u2013332 (2009)","DOI":"10.1145\/1536414.1536459"},{"key":"792_CR26","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0167-6377(96)00016-8","volume":"19","author":"ST McCormick","year":"1996","unstructured":"McCormick, S.T.: Submodular containment is hard, even for networks. Oper. Res. Lett. 19, 95\u201399 (1996)","journal-title":"Oper. Res. Lett."},{"key":"792_CR27","first-page":"321","volume-title":"Discrete Optimization, Handbooks in Operations Research and Management Science, Chap. 7","author":"ST McCormick","year":"2006","unstructured":"McCormick, S.T.: Submodular function minimization. In: Aardal, K., Nemhauser, G., Weismantel, R. (eds.) Discrete Optimization, Handbooks in Operations Research and Management Science, Chap. 7, vol. 12, pp. 321\u2013391. Elsevier Science Publishers, Berlin (2006)"},{"key":"792_CR28","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1137\/0121018","volume":"21","author":"BL Miller","year":"1971","unstructured":"Miller, B.L.: On minimizing nonseparable functions defined on the integers with an inventory applications. SIAM J. Appl. Math. 21, 166\u2013185 (1971)","journal-title":"SIAM J. Appl. Math."},{"key":"792_CR29","doi-asserted-by":"crossref","unstructured":"Moriguchi, S., Murota, K.: Discrete Hessian matrix for L-convex functions. In: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E83-A, pp. 1104\u20131108 (2005)","DOI":"10.1093\/ietfec\/e88-a.5.1104"},{"key":"792_CR30","doi-asserted-by":"crossref","first-page":"48","DOI":"10.15807\/jorsj.55.48","volume":"55","author":"S Moriguchi","year":"2012","unstructured":"Moriguchi, S., Murota, K.: On discrete Hessian matrix and convex extensibility. J. Oper. Res. Soc. Jpn. 55, 48\u201362 (2012)","journal-title":"J. Oper. Res. Soc. Jpn."},{"key":"792_CR31","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1137\/S0895480195279994","volume":"9","author":"K Murota","year":"1996","unstructured":"Murota, K.: Valuated matroid intersection, I: optimality criteria. SIAM J. Discret. Math. 9, 545\u2013561 (1996)","journal-title":"SIAM J. Discret. Math."},{"key":"792_CR32","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1137\/S0895480195280009","volume":"9","author":"K Murota","year":"1996","unstructured":"Murota, K.: Valuated matroid intersection, II: algorithms. SIAM J. Discret. Math. 9, 562\u2013576 (1996)","journal-title":"SIAM J. Discret. Math."},{"key":"792_CR33","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1006\/jctb.1996.1723","volume":"69","author":"K Murota","year":"1997","unstructured":"Murota, K.: Matroid valuation on independent sets. J. Combinatorial Theory Ser. B 69, 59\u201378 (1997)","journal-title":"J. Combinatorial Theory Ser. B"},{"key":"792_CR34","first-page":"313","volume":"83","author":"K Murota","year":"1998","unstructured":"Murota, K.: Discrete convex analysis. Math. Program. 83, 313\u2013371 (1998)","journal-title":"Math. Program."},{"key":"792_CR35","volume-title":"Matrices and Matroids for Systems Analysis","author":"K Murota","year":"2000","unstructured":"Murota, K.: Matrices and Matroids for Systems Analysis. Springer, Berlin (2000)"},{"key":"792_CR36","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718508","volume-title":"Discrete Convex Analysis","author":"K Murota","year":"2003","unstructured":"Murota, K.: Discrete Convex Analysis. Society for Industrial and Applied Mathematics, Philadelphia (2003)"},{"key":"792_CR37","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/978-3-540-76796-1_11","volume-title":"Research Trends in Combinatorial Optimization, Chap. 11","author":"K Murota","year":"2009","unstructured":"Murota, K.: Recent developments in discrete convex analysis. In: Cook, W., Lov\u00e1sz, L., Vygen, J. (eds.) Research Trends in Combinatorial Optimization, Chap. 11, pp. 219\u2013260. Springer, Berlin (2009)"},{"key":"792_CR38","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1287\/moor.24.1.95","volume":"24","author":"K Murota","year":"1999","unstructured":"Murota, K., Shioura, A.: M-convex function on generalized polymatroid. Math. Oper. Res. 24, 95\u2013105 (1999)","journal-title":"Math. Oper. Res."},{"key":"792_CR39","doi-asserted-by":"crossref","unstructured":"Murota, K., Shioura, A.: Exact bounds for steepest descent algorithms of L-convex function minimization. Oper. Res. Lett. to appear (2014)","DOI":"10.1016\/j.orl.2014.06.005"},{"key":"792_CR40","unstructured":"Narasimhan, M., Bilmes, J.: A submodular-supermodular procedure with applications to discriminative structure learning. In: Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence, pp. 404\u2013412 (2005)"},{"key":"792_CR41","doi-asserted-by":"crossref","DOI":"10.4171\/093","volume-title":"Nonlinear Discrete Optimization: An Algorithmic Theory","author":"S Onn","year":"2010","unstructured":"Onn, S.: Nonlinear Discrete Optimization: An Algorithmic Theory. European Mathematical Society, Zurich (2010)"},{"key":"792_CR42","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/s10107-007-0189-2","volume":"118","author":"JB Orlin","year":"2009","unstructured":"Orlin, J.B.: A faster strongly polynomial time algorithm for submodular function minimization. Math. Program. Ser. A 118, 237\u2013251 (2009)","journal-title":"Math. Program. Ser. A"},{"key":"792_CR43","doi-asserted-by":"crossref","unstructured":"Queyranne, M., Tardella, F.: Submodular function minimization in $$\\mathbb{Z}^n$$ Z n and searching in Monge arrays. Unpublished manuscript, Presented by M. Queyranne at CTW04 (Cologne Twente Workshop 2004), Electronic Notes in Discrete Mathematics, vol. 17, p. 5 (2004)","DOI":"10.1016\/j.endm.2004.03.003"},{"key":"792_CR44","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)"},{"key":"792_CR45","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1017\/S0004972700010844","volume":"20","author":"I Singer","year":"1979","unstructured":"Singer, I.: A Fenchel-Rockafellar type duality theorem for maximization. Bull. Aust. Math. Soc. 20, 193\u2013198 (1979)","journal-title":"Bull. Aust. Math. Soc."},{"key":"792_CR46","doi-asserted-by":"crossref","unstructured":"Tao, P.D., El Bernoussi, S.: Duality in D.C. (difference of convex functions) optimization: Subgradient methods. In: Hoffman, K.H., Zowe, J., Hiriart-Urruty, J.B., Lemar\u00e9chal, C. (eds.) Trends in Mathematical Optimization, International Series of Numerical Mathematics, vol. 84, pp. 277\u2013293. Basel, Birkh\u00e4user (1987)","DOI":"10.1007\/978-3-0348-9297-1_18"},{"key":"792_CR47","first-page":"289","volume":"22","author":"PD Tao","year":"1997","unstructured":"Tao, P.D.: Hoai An, L.T.: Convex analysis approach to D.C. programming: Theory, algorithms and applications. Acta Math. Vietnam. 22, 289\u2013355 (1997)","journal-title":"Acta Math. Vietnam."},{"key":"792_CR48","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF00250669","volume":"71","author":"JF Toland","year":"1979","unstructured":"Toland, J.F.: A duality principle for non-convex optimisation and the calculus of variations. Arch. Ration. Mech. Anal. 71, 41\u201361 (1979)","journal-title":"Arch. Ration. Mech. Anal."},{"key":"792_CR49","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1287\/opre.26.2.305","volume":"26","author":"DM Topkis","year":"1978","unstructured":"Topkis, D.M.: Minimizing a submodular function on a lattice. Oper. Res. 26, 305\u2013321 (1978)","journal-title":"Oper. Res."},{"key":"792_CR50","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1007\/BFb0121159","volume":"30","author":"H Tuy","year":"1987","unstructured":"Tuy, H.: Global minimization of a difference of two convex functions. Math. Program. Study 30, 150\u2013182 (1987)","journal-title":"Math. Program. Study"},{"key":"792_CR51","doi-asserted-by":"crossref","unstructured":"Tuy, H.: D.C. optimization: Theory, methods and algorithms. In: Horst, R., Pardalos, P.M. (eds.) Handbook of Global Optimization, pp. 149\u2013216. Kluwer Academic Publishers, Dordrecht (1995)","DOI":"10.1007\/978-1-4615-2025-2_4"},{"key":"792_CR52","doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 67\u201374 (2008)","DOI":"10.1145\/1374376.1374389"},{"key":"792_CR53","doi-asserted-by":"crossref","first-page":"915","DOI":"10.1162\/08997660360581958","volume":"15","author":"AL Yuille","year":"2003","unstructured":"Yuille, A.L., Rangarajan, A.: The concave-convex procedure. Neural Comput. 15, 915\u2013936 (2003)","journal-title":"Neural Comput."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-014-0792-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-014-0792-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-014-0792-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,12]],"date-time":"2019-08-12T05:00:24Z","timestamp":1565586024000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-014-0792-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7,2]]},"references-count":53,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2015,8]]}},"alternative-id":["792"],"URL":"https:\/\/doi.org\/10.1007\/s10107-014-0792-y","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,7,2]]}}}