{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T18:56:54Z","timestamp":1778871414508,"version":"3.51.4"},"publisher-location":"Cham","reference-count":33,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030535513","type":"print"},{"value":"9783030535520","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"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":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-53552-0_8","type":"book-chapter","created":{"date-parts":[[2020,7,17]],"date-time":"2020-07-17T16:50:23Z","timestamp":1595004623000},"page":"52-67","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["A Class of Linear Programs Solvable by Coordinate-Wise Minimization"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1944-6569","authenticated-orcid":false,"given":"Tom\u00e1\u0161","family":"Dlask","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6161-7157","authenticated-orcid":false,"given":"Tom\u00e1\u0161","family":"Werner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,7,18]]},"reference":[{"key":"8_CR1","unstructured":"Ansotegui, C., Bacchus, F., J\u00e4rvisalo, M., Martins, R., et al.: MaxSAT Evaluation 2017 (2017). https:\/\/helda.helsinki.fi\/bitstream\/handle\/10138\/233112\/mse17proc.pdf"},{"key":"8_CR2","unstructured":"Bacchus, F., J\u00e4rvisalo, M., Martins, R.: MaxSAT evaluation 2018: new developments and detailed results. J. Satisf. Boolean Model. Comput. 11(1), 99\u2013131 (2019). instances available at https:\/\/maxsat-evaluations.github.io\/"},{"key":"8_CR3","unstructured":"Bacchus, F., J\u00e4rvisalo, M.J., Martins, R., et al.: MaxSAT evaluation 2018 (2018). https:\/\/helda.helsinki.fi\/bitstream\/handle\/10138\/237139\/mse18_proceedings.pdf"},{"key":"8_CR4","volume-title":"Nonlinear Programming","author":"DP Bertsekas","year":"1999","unstructured":"Bertsekas, D.P.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1999)","edition":"2"},{"issue":"1","key":"8_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/2200000016","volume":"3","author":"S Boyd","year":"2011","unstructured":"Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3(1), 1\u2013122 (2011)","journal-title":"Found. Trends Mach. Learn."},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"Boykov, Y., Lempitsky, V.S.: From photohulls to photoflux optimization. In: Proceedings of the British Machine Conference, vol. 3, p. 27. Citeseer (2006)","DOI":"10.5244\/C.20.117"},{"key":"8_CR7","unstructured":"Boykov, Y., Veksler, O., Zabih, R.: Markov random fields with efficient approximations. In: Proceedings of 1998 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Cat. No. 98CB36231), pp. 648\u2013655. IEEE (1998)"},{"issue":"1","key":"8_CR8","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/s10851-010-0251-1","volume":"40","author":"A Chambolle","year":"2011","unstructured":"Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40(1), 120\u2013145 (2011). https:\/\/doi.org\/10.1007\/s10851-010-0251-1","journal-title":"J. Math. Imaging Vis."},{"issue":"5","key":"8_CR9","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/S0167-6377(99)00056-5","volume":"25","author":"FA Chudak","year":"1999","unstructured":"Chudak, F.A., Hochbaum, D.S.: A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine. Oper. Res. Lett. 25(5), 199\u2013204 (1999)","journal-title":"Oper. Res. Lett."},{"key":"8_CR10","doi-asserted-by":"crossref","unstructured":"Dlask, T., Werner, T.: A class of linear programs solvable by coordinate-wise minimization. $${\\rm arXiv}.{\\rm org}$$ (2020)","DOI":"10.1007\/978-3-030-53552-0_8"},{"key":"8_CR11","volume-title":"Flows in Networks","author":"D Fulkerson","year":"1962","unstructured":"Fulkerson, D., Ford, L.: Flows in Networks. Princeton University Press, Princeton (1962)"},{"key":"8_CR12","unstructured":"Globerson, A., Jaakkola, T.: Fixing max-product: Convergent message passing algorithms for MAP LP-relaxations. In: Neural Information Processing Systems, pp. 553\u2013560 (2008)"},{"issue":"2","key":"8_CR13","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/S0377-2217(02)00071-1","volume":"140","author":"DS Hochbaum","year":"2002","unstructured":"Hochbaum, D.S.: Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations. Eur. J. Oper. Res. 140(2), 291\u2013321 (2002)","journal-title":"Eur. J. Oper. Res."},{"issue":"4","key":"8_CR14","first-page":"544","volume":"43","author":"DS Hochbaum","year":"1997","unstructured":"Hochbaum, D.S., Pathria, A.: Forest harvesting and minimum cuts: a new approach to handling spatial constraints. For. Sci. 43(4), 544\u2013554 (1997)","journal-title":"For. Sci."},{"issue":"1\u20133","key":"8_CR15","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0166-218X(00)00244-4","volume":"107","author":"DS Hochbaum","year":"2000","unstructured":"Hochbaum, D.S., Pathria, A.: Approximating a generalization of MAX 2SAT and MIN 2SAT. Discret. Appl. Math. 107(1\u20133), 41\u201359 (2000)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"8_CR16","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/s11263-015-0809-x","volume":"115","author":"JH Kappes","year":"2015","unstructured":"Kappes, J.H., et al.: A comparative study of modern inference techniques for structured discrete energy minimization problems. Int. J. Comput. Vis. 115(2), 155\u2013184 (2015). https:\/\/doi.org\/10.1007\/s11263-015-0809-x","journal-title":"Int. J. Comput. Vis."},{"issue":"2","key":"8_CR17","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1137\/S0895480191220836","volume":"7","author":"R Kohli","year":"1994","unstructured":"Kohli, R., Krishnamurti, R., Mirchandani, P.: The minimum satisfiability problem. SIAM J. Discret. Math. 7(2), 275\u2013283 (1994)","journal-title":"SIAM J. Discret. Math."},{"issue":"10","key":"8_CR18","doi-asserted-by":"publisher","first-page":"1568","DOI":"10.1109\/TPAMI.2006.200","volume":"28","author":"V Kolmogorov","year":"2006","unstructured":"Kolmogorov, V.: Convergent tree-reweighted message passing for energy minimization. IEEE Trans. Pattern Anal. Mach. Intell. 28(10), 1568\u20131583 (2006)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"5","key":"8_CR19","doi-asserted-by":"publisher","first-page":"919","DOI":"10.1109\/TPAMI.2014.2363465","volume":"37","author":"V Kolmogorov","year":"2015","unstructured":"Kolmogorov, V.: A new look at reweighted message passing. IEEE Trans. Pattern Anal. Mach. Intell. 37(5), 919\u2013930 (2015)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"8_CR20","unstructured":"Kolmogorov, V., Zabih, R.: Computing visual correspondence with occlusions via graph cuts, Technical report. Cornell University (2001)"},{"key":"8_CR21","unstructured":"Kovalevsky, V.A., Koval, V.K.: A diffusion algorithm for decreasing the energy of the max-sum labeling problem. Glushkov Institute of Cybernetics. Kiev, USSR (approx. 1975, unpublished)"},{"key":"8_CR22","doi-asserted-by":"crossref","unstructured":"Lempitsky, V., Boykov, Y.: Global optimization for shape fitting. In: 2007 IEEE Conference on Computer Vision and Pattern Recognition, pp. 1\u20138. IEEE (2007)","DOI":"10.1109\/CVPR.2007.383293"},{"key":"8_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/11744078_18","volume-title":"Computer Vision \u2013 ECCV 2006","author":"V Lempitsky","year":"2006","unstructured":"Lempitsky, V., Boykov, Y., Ivanov, D.: Oriented visibility for multiview reconstruction. In: Leonardis, A., Bischof, H., Pinz, A. (eds.) ECCV 2006. LNCS, vol. 3953, pp. 226\u2013238. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11744078_18"},{"key":"8_CR24","unstructured":"Pr\u016f\u0161a, D., Werner, T.: LP relaxation of the Potts labeling problem is as hard as any linear program. IEEE Trans. Pattern Anal. Mach. Intell. 39(7), 1469\u20131475 (2017)"},{"issue":"1\u20133","key":"8_CR25","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1023\/A:1014573219977","volume":"47","author":"D Scharstein","year":"2002","unstructured":"Scharstein, D., Szeliski, R.: A taxonomy and evaluation of dense two-frame stereo correspondence algorithms. Int. J. Comput. Vis. 47(1\u20133), 7\u201342 (2002). https:\/\/doi.org\/10.1023\/A:1014573219977","journal-title":"Int. J. Comput. Vis."},{"key":"8_CR26","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/s10559-011-9300-z","volume":"47","author":"MI Schlesinger","year":"2011","unstructured":"Schlesinger, M.I., Antoniuk, K.: Diffusion algorithms and structural recognition optimization problems. Cybern. Syst. Anal. 47, 175\u2013192 (2011). https:\/\/doi.org\/10.1007\/s10559-011-9300-z","journal-title":"Cybern. Syst. Anal."},{"issue":"6","key":"8_CR27","doi-asserted-by":"publisher","first-page":"1068","DOI":"10.1109\/TPAMI.2007.70844","volume":"30","author":"R Szeliski","year":"2008","unstructured":"Szeliski, R., et al.: A comparative study of energy minimization methods for Markov random fields with smoothness-based priors. IEEE Trans. Pattern Anal. Mach. Intell. 30(6), 1068\u20131080 (2008)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"3","key":"8_CR28","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1023\/A:1017501703105","volume":"109","author":"P Tseng","year":"2001","unstructured":"Tseng, P.: Convergence of a block coordinate descent method for nondifferentiable minimization. J. Optim. Theor. Appl. 109(3), 475\u2013494 (2001). https:\/\/doi.org\/10.1023\/A:1017501703105","journal-title":"J. Optim. Theor. Appl."},{"issue":"7","key":"8_CR29","doi-asserted-by":"publisher","first-page":"1165","DOI":"10.1109\/TPAMI.2007.1036","volume":"29","author":"T Werner","year":"2007","unstructured":"Werner, T.: A linear programming approach to max-sum problem: a review. IEEE Trans. Pattern Anal. Mach. Intell. 29(7), 1165\u20131179 (2007)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"8_CR30","doi-asserted-by":"crossref","unstructured":"Werner, T., Pr\u016f\u0161a, D., Dlask, T.: Relative interior rule in block-coordinate descent. In: Accepted to IEEE\/CVF Conference on Computer Vision and Pattern Recognition (2020)","DOI":"10.1109\/CVPR42600.2020.00758"},{"key":"8_CR31","unstructured":"Werner, T., Pr\u016f\u0161a, D.: Relative interior rule in block-coordinate minimization (2019). arXiv:1910.09488"},{"issue":"1","key":"8_CR32","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10107-015-0892-3","volume":"151","author":"SJ Wright","year":"2015","unstructured":"Wright, S.J.: Coordinate descent algorithms. Math. Program. 151(1), 3\u201334 (2015). https:\/\/doi.org\/10.1007\/s10107-015-0892-3","journal-title":"Math. Program."},{"key":"8_CR33","unstructured":"Xu, K., Li, W.: Many hard examples in exact phase transitions with application to generating hard satisfiable instances. $${\\rm arXiv}.{\\rm org}$$ (2003). Instances available at http:\/\/sites.nlsde.buaa.edu.cn\/~kexu\/benchmarks\/max-sat-benchmarks.htm"}],"container-title":["Lecture Notes in Computer Science","Learning and Intelligent Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-53552-0_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,25]],"date-time":"2021-03-25T20:07:44Z","timestamp":1616702864000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-53552-0_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030535513","9783030535520"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-53552-0_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"18 July 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LION","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Learning and Intelligent Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Athens","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Greece","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 May 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 May 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"lion2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.caopt.com\/LION14\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}