{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,14]],"date-time":"2026-01-14T23:43:26Z","timestamp":1768434206881,"version":"3.49.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2019,10,29]],"date-time":"2019-10-29T00:00:00Z","timestamp":1572307200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,10,29]],"date-time":"2019-10-29T00:00:00Z","timestamp":1572307200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2019,12]]},"DOI":"10.1007\/s00493-019-3900-1","type":"journal-article","created":{"date-parts":[[2019,10,30]],"date-time":"2019-10-30T21:05:20Z","timestamp":1572469520000},"page":"1351-1386","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Submodular Minimization Under Congruency Constraints"],"prefix":"10.1007","volume":"39","author":[{"given":"Martin","family":"N\u00e4gele","sequence":"first","affiliation":[]},{"given":"Benny","family":"Sudakov","sequence":"additional","affiliation":[]},{"given":"Rico","family":"Zenklusen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,10,29]]},"reference":[{"key":"3900_CR1","first-page":"1206","volume-title":"Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC)","author":"S Artmann","year":"2017","unstructured":"S. Artmann, R. Weismantel and R. Zenklusen: A strongly polynomial algorithm for bimodular integer linear programming, in: Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC), 1206\u20131219, 2017."},{"key":"3900_CR2","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/0012-365X(87)90097-5","volume":"66","author":"F Barahona","year":"1987","unstructured":"F. Barahona and M. Conforti: A construction for binary matroids, Discrete Mathematics66 (1987), 213\u2013218.","journal-title":"Discrete Mathematics"},{"key":"3900_CR3","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/BF01263424","volume":"4","author":"D A Mix Barrington","year":"1994","unstructured":"D. A. Mix Barrington, R. Beigel and S. Rudich: Representing boolean functions as polynomials modulo composite numbers, Computational Complexity4 (1994), 367\u2013382.","journal-title":"Computational Complexity"},{"key":"3900_CR4","first-page":"1220","volume-title":"Proceedings of 49th Annual ACM Symposium on the Theory of Computing (STOC)","author":"D Chakrabarty","year":"2017","unstructured":"D. Chakrabarty, A. Sidford, Y. T. Lee, and Wong S. C: Subquadratic submodular function minimization, in: Proceedings of 49th Annual ACM Symposium on the Theory of Computing (STOC), 1220\u20131231, 2017."},{"key":"3900_CR5","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1287\/moor.12.2.193","volume":"12","author":"M Conforti","year":"1987","unstructured":"M. Conforti and M. R. Rao: Some new matroids on graphs: Cut sets and the max cut problem, Mathematics of Operations Research12 (1987), 193\u2013204.","journal-title":"Mathematics of Operations Research"},{"key":"3900_CR6","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/BF02579361","volume":"5","author":"W H Cunningham","year":"1985","unstructured":"W. H. Cunningham: On submodular function minimization, Combinatorica5 (1985), 185\u2013192.","journal-title":"Combinatorica"},{"key":"3900_CR7","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/BF02579457","volume":"1","author":"P Frankl","year":"1981","unstructured":"P. Frankl and R. M. Wilson: in:tersection theorems with geometric consequences, Combinatorica1 (1981), 357\u2013368.","journal-title":"Combinatorica"},{"key":"3900_CR8","volume-title":"Submodular Functions and Optimization","author":"S Fujishige","year":"2005","unstructured":"S. Fujishige: Submodular Functions and Optimization, Elsevier, 2005."},{"key":"3900_CR9","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/s00493-016-3445-3","volume":"38","author":"J Geelen","year":"2017","unstructured":"J. Geelen and R. Kapadia: Computing girth and cogirth in perturbed graphic matroids, Combinatorica38 (2017), 167\u2013191.","journal-title":"Combinatorica"},{"key":"3900_CR10","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/BF01192523","volume":"15","author":"M X Goemans","year":"1995","unstructured":"M. X. Goemans and V. S. Ramakrishnan: Minimizing submodular functions over families of sets, Combinatorica15 (1995), 499\u2013513.","journal-title":"Combinatorica"},{"key":"3900_CR11","volume-title":"Private communication","author":"S Gopi","year":"2017","unstructured":"S. Gopi: Private communication, 2017."},{"key":"3900_CR12","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s004930070032","volume":"20","author":"V Grolmusz","year":"2000","unstructured":"V. Grolmusz: Superpolynomial size set-systems with restricted intersections mod 6 and explicit ramsey graphs, Combinatorica20 (2000), 71\u201386.","journal-title":"Combinatorica"},{"key":"3900_CR13","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz and A. Schrijver: The ellipsoid method and its consequences in combinatorial optimization, Combinatorica1 (1981), 169\u2013197.","journal-title":"Combinatorica"},{"key":"3900_CR14","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/BF02579139","volume":"4","author":"M Gr\u00f6tschel","year":"1984","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz and A. Schrijver: Corrigendum to our paper \u201cThe ellipsoid method and its consequences in combinatorial optimization\u201d, Combinatorica4 (1984), 291\u2013295.","journal-title":"Combinatorica"},{"key":"3900_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-78240-4","volume-title":"Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics","author":"M Gr\u00f6tschel","year":"1993","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz and L. Schrijver: Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics, Springer, second corrected edition, 1993.","edition":"second correcte"},{"key":"3900_CR16","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/s10107-006-0084-2","volume":"112","author":"S Iwata","year":"2008","unstructured":"S. Iwata: Submodular function minimization, Mathematical Programming, Series B112 (2008), 45\u201364.","journal-title":"Mathematical Programming, Series B"},{"key":"3900_CR17","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1145\/502090.502096","volume":"48","author":"S Iwata","year":"2001","unstructured":"S. Iwata, L. Fleischer and S. Fujishige: A combinatorial strongly polynomial algorithm for minimizing submodular functions, Journal of the ACM48 (2001), 761\u2013777.","journal-title":"Journal of the ACM"},{"key":"3900_CR18","doi-asserted-by":"publisher","first-page":"1230","DOI":"10.1137\/1.9781611973068.133","volume-title":"Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"S Iwata","year":"2009","unstructured":"S. Iwata and J. B. Orlin: A simple combinatorial algorithm for submodular function minimization, in: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1230\u20131237, 2009."},{"key":"3900_CR19","first-page":"21","volume-title":"Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"D R Karger","year":"1993","unstructured":"D. R. Karger: Global min-cuts in RNC, and other rami_cations of a simple minout algorithm, in: Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 21\u201330, 1993."},{"key":"3900_CR20","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1145\/234533.234534","volume":"43","author":"D R Karger","year":"1996","unstructured":"D. R. Karger and C. Stein: A new approach to the minimum cut problem, Journal of the ACM43 (1996), 601\u2013640.","journal-title":"Journal of the ACM"},{"key":"3900_CR21","first-page":"1049","volume-title":"Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Y T Lee","year":"2015","unstructured":"Y. T. Lee, A. Sidford and S. C. Wong: 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), 1049\u20131065, 2015."},{"key":"3900_CR22","first-page":"321","volume-title":"Discrete Optimization, volumes 12 of Handbooks in Operations Research and Management Science","author":"S T MCormick","year":"2005","unstructured":"S. T. MCormick: Submodular function minimization, in: Discrete Optimization, volumes 12 of Handbooks in Operations Research and Management Science, 321\u2013391. Elsevier, 2005, Updated version of 2013 available at: \nhttps:\/\/doi.org\/pdfs.semanticscholar.org\/903d\/12346be328623e41e7bea2791a6e6df570fc.pdf."},{"key":"3900_CR23","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1287\/moor.7.1.67","volume":"7","author":"M W Padberg","year":"1982","unstructured":"M. W. Padberg and M. R. Rao: Odd minimum cut-sets and b-matchings, Mathematics of Operations Research7 (1982), 67\u201380.","journal-title":"Mathematics of Operations Research"},{"key":"3900_CR24","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1006\/jctb.2000.1989","volume":"80","author":"A Schrijver","year":"2000","unstructured":"A. Schrijver: A combinatorial algorithm minimizing submodular functions in strongly polynomial time, Journal of Combinatorial Theory, Series B80 (2000), 346\u2013355.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"3900_CR25","volume-title":"Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"A. Schrijver: Combinatorial Optimization, Polyhedra and Efficiency, Springer, 2003."},{"key":"3900_CR26","doi-asserted-by":"publisher","first-page":"1715","DOI":"10.1137\/100783352","volume":"40","author":"Z Svitkina","year":"2011","unstructured":"Z. Svitkina and L. Fleischer: Submodular approximation: Sampling-based algorithms and lower bounds, SIAM Journal on Computing40 (2011), 1715\u20131737.","journal-title":"SIAM Journal on Computing"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-019-3900-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-019-3900-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-019-3900-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,28]],"date-time":"2020-10-28T00:13:10Z","timestamp":1603843990000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-019-3900-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,29]]},"references-count":26,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["3900"],"URL":"https:\/\/doi.org\/10.1007\/s00493-019-3900-1","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,29]]},"assertion":[{"value":"10 November 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 August 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 October 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}