{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:50Z","timestamp":1740122390949,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,5,20]],"date-time":"2017-05-20T00:00:00Z","timestamp":1495238400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"JST ERATO Grant Number JPMJER1305","award":["JPMJER1305"],"award-info":[{"award-number":["JPMJER1305"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2018,10]]},"DOI":"10.1007\/s10878-017-0136-y","type":"journal-article","created":{"date-parts":[[2017,5,20]],"date-time":"2017-05-20T15:07:03Z","timestamp":1495292823000},"page":"678-708","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On a general framework for network representability in discrete optimization"],"prefix":"10.1007","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6794-3543","authenticated-orcid":false,"given":"Yuni","family":"Iwamasa","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,20]]},"reference":[{"issue":"2\u20133","key":"136_CR1","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1561\/2200000039","volume":"6","author":"F Bach","year":"2013","unstructured":"Bach F (2013) Learning with submodular functions: a convex optimization perspective. Found Trends Mach Learn 6(2\u20133):145\u2013373","journal-title":"Found Trends Mach Learn"},{"key":"136_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0166-218X(85)90035-6","volume":"12","author":"A Billionnet","year":"1985","unstructured":"Billionnet A, Minoux M (1985) Maximizing a supermodular pseudoboolean function: a polynomial algorithm for supermodular cubic functions. Discrete Appl Math 12:1\u201311","journal-title":"Discrete Appl Math"},{"issue":"5","key":"136_CR3","doi-asserted-by":"crossref","first-page":"1915","DOI":"10.1137\/130906398","volume":"42","author":"DA Cohen","year":"2013","unstructured":"Cohen DA, Cooper MC, Creed P, Jeavons PG, \u017divn\u00fd S (2013) An algebraic theory of complexity for discrete optimization. SIAM J Comput 42(5):1915\u20131939","journal-title":"SIAM J Comput"},{"key":"136_CR4","volume-title":"Submodular functions and optimization","author":"S Fujishige","year":"2005","unstructured":"Fujishige S (2005) Submodular functions and optimization, 2nd edn. Elsevier, Amsterdam","edition":"2"},{"key":"136_CR5","unstructured":"Fujishige S, Kir\u00e1ly T, Makino K, Takazawa K, Tanigawa S (2015) Minimizing submodular functions on diamonds via generalized fractional matroid matchings. RIMS technical reports, RIMS-1812"},{"key":"136_CR6","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1111\/j.2517-6161.1989.tb01764.x","volume":"51","author":"G Greig","year":"1989","unstructured":"Greig G, Porteous B, Seheult A (1989) Exact minimum a posteriori estimation for binary images. J R Stat Soc Ser B 51:271\u2013279","journal-title":"J R Stat Soc Ser B"},{"key":"136_CR7","doi-asserted-by":"crossref","unstructured":"Gridchyn I, Kolmogorov V (2013) Potts model, parametric maxflow and $$k$$ k -submodular functions. In: Proceedings of international conference on computer vision (ICCV\u201913), pp 2320\u20132327","DOI":"10.1109\/ICCV.2013.288"},{"key":"136_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric algorithms and combinatorial optimization","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel M, Lov\u00e1sz L, Schrijver A (1988) Geometric algorithms and combinatorial optimization. Springer, Berlin"},{"key":"136_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.disopt.2015.07.001","volume":"18","author":"H Hirai","year":"2015","unstructured":"Hirai H (2015) L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem. Discrete Optim 18:1\u201337","journal-title":"Discrete Optim"},{"key":"136_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10107-014-0824-7","volume":"155","author":"H Hirai","year":"2016","unstructured":"Hirai H (2016) Discrete convexity and polynomial solvability in minimum 0-extension problems. Math Program Ser A 155:1\u201355","journal-title":"Math Program Ser A"},{"key":"136_CR11","doi-asserted-by":"crossref","unstructured":"Huber A, Kolmogorov V (2012) Towards minimizing $$k$$ k -submodular functions. In: Proceedings of the 2nd international symposium on combinatorial optimization (ISCO\u201912). Springer, Berlin, pp 451\u2013462","DOI":"10.1007\/978-3-642-32147-4_40"},{"key":"136_CR12","unstructured":"Ishii Y (2014) On a representation of $$k$$ k -submodular functions by a skew-symmetric network. Master thesis, The University of Tokyo, (in Japanese)"},{"issue":"3","key":"136_CR13","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1287\/opre.13.3.388","volume":"13","author":"PL Iv\u0103nescu","year":"1965","unstructured":"Iv\u0103nescu PL (1965) Some network flow problems solved with pseudo-boolean programming. Oper Res 13(3):388\u2013399","journal-title":"Oper Res"},{"issue":"4","key":"136_CR14","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1145\/502090.502096","volume":"48","author":"S Iwata","year":"2001","unstructured":"Iwata S, Fleischer L, Fujishige S (2001) A combinatorial strongly polynomial algorithm for minimizing submodular functions. J ACM 48(4):761\u2013777","journal-title":"J ACM"},{"issue":"4","key":"136_CR15","doi-asserted-by":"crossref","first-page":"1377","DOI":"10.1137\/140962838","volume":"45","author":"Y Iwata","year":"2016","unstructured":"Iwata Y, Wahlstr\u00f6m M, Yoshida Y (2016) Half-integrality, LP-branching and FPT algorithms. SIAM J Comput 45(4):1377\u20131411","journal-title":"SIAM J Comput"},{"key":"136_CR16","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/BF01581152","volume":"66","author":"AV Karzanov","year":"1994","unstructured":"Karzanov AV (1994) Minimum cost multiflows in undirected networks. Math Program 66:313\u2013325","journal-title":"Math Program"},{"issue":"4","key":"136_CR17","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1007\/s004930050040","volume":"18","author":"AV Karzanov","year":"1998","unstructured":"Karzanov AV (1998) A combinatorial algorithm for the minimum $$(2, r)$$ ( 2 , r ) -metric problem and some generalization. Combinatorica 18(4):549\u2013568","journal-title":"Combinatorica"},{"issue":"1","key":"136_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/130945648","volume":"44","author":"V Kolmogorov","year":"2015","unstructured":"Kolmogorov V, Thapper J, \u017divn\u00fd S (2015) The power of linear programming for general-valued CSPs. SIAM J Comput 44(1):1\u201336","journal-title":"SIAM J Comput"},{"issue":"2","key":"136_CR19","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1109\/TPAMI.2004.1262177","volume":"26","author":"V Kolmogorov","year":"2004","unstructured":"Kolmogorov V, Zabih R (2004) What energy functions can be minimized via graph cuts? IEEE Trans Pattern Anal Mach Intell 26(2):147\u2013159","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"key":"136_CR20","doi-asserted-by":"crossref","unstructured":"Kozik M, Ochremiak J (2015) Algebraic properties of valued constraint satisfaction problem. In: Proceedings of the 42nd international colloquium on automata, languages and programming (ICALP\u201915), pp 846\u2013858","DOI":"10.1007\/978-3-662-47672-7_69"},{"key":"136_CR21","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1016\/j.disopt.2011.04.001","volume":"8","author":"F Kuivinen","year":"2011","unstructured":"Kuivinen F (2011) On the complexity of submodular function minimisation on diamonds. Discrete Optim 8:459\u2013477","journal-title":"Discrete Optim"},{"key":"136_CR22","doi-asserted-by":"crossref","unstructured":"Lee YT, Sidford A, Wong SC (2015) A faster cutting plane method and its implications for combinatorial and convex optimization. In: Proceedings of the 56th annual IEEE symposium on foundations of computer science (FOCS\u201915), arXiv:1508.04874v2","DOI":"10.1109\/FOCS.2015.68"},{"key":"136_CR23","doi-asserted-by":"crossref","unstructured":"Orlin JB (2013) Max flows in $${O}(nm)$$ O ( n m ) time, or better. In: Proceedings of the 45th annual ACM symposium on the theory of computing (STOC\u201913), pp 765\u2013774","DOI":"10.1145\/2488608.2488705"},{"key":"136_CR24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.dam.2016.11.022","volume":"220","author":"S Ramalingam","year":"2017","unstructured":"Ramalingam S, Russell C, Ladick\u00fd L, Torr PHS (2017) Efficient minimization of higher order submodular functions using monotonic Boolean functions. Discrete Appl Math 220:1\u201319","journal-title":"Discrete Appl Math"},{"key":"136_CR25","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1006\/jctb.2000.1989","volume":"80","author":"A Schrijver","year":"2000","unstructured":"Schrijver A (2000) A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J Comb Theory Ser B 80:346\u2013355","journal-title":"J Comb Theory Ser B"},{"key":"136_CR26","doi-asserted-by":"crossref","unstructured":"Thapper J, \u017divn\u00fd S (2012) The power of linear programming for valued CSPs. In: Proceedings of the 53rd annual IEEE symposium on foundations of computer science (FOCS\u201912). IEEE, pp 669\u2013678","DOI":"10.1109\/FOCS.2012.25"},{"key":"136_CR27","doi-asserted-by":"crossref","unstructured":"Thapper J, \u017divn\u00fd S (2017) The power of Sherali-Adams relaxations for general-valued CSPs. arXiv:1606.02577v2","DOI":"10.1109\/LICS.2017.8005087"},{"key":"136_CR28","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-33974-5","volume-title":"The complexity of valued constraint satisfaction problems","author":"S \u017divn\u00fd","year":"2012","unstructured":"\u017divn\u00fd S (2012) The complexity of valued constraint satisfaction problems. Springer, Heidelberg"},{"issue":"15","key":"136_CR29","doi-asserted-by":"crossref","first-page":"3347","DOI":"10.1016\/j.dam.2009.07.001","volume":"157","author":"S \u017divn\u00fd","year":"2009","unstructured":"\u017divn\u00fd S, Cohen DA, Jeavons PG (2009) The expressive power of binary submodular functions. Discrete Appl Math 157(15):3347\u20133358","journal-title":"Discrete Appl Math"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-017-0136-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0136-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0136-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,24]],"date-time":"2024-06-24T07:17:51Z","timestamp":1719213471000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-017-0136-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,20]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,10]]}},"alternative-id":["136"],"URL":"https:\/\/doi.org\/10.1007\/s10878-017-0136-y","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2017,5,20]]}}}