[{"oa":1,"publisher":"IEEE","quality_controlled":"1","date_created":"2018-12-11T11:49:11Z","date_published":"2017-01-01T00:00:00Z","doi":"10.1109/CVPR.2017.747","page":"7062-7071","day":"01","year":"2017","isi":1,"has_accepted_license":"1","project":[{"grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice","call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425"}],"title":"A study of lagrangean decompositions and dual ascent solvers for graph matching","article_processing_charge":"No","external_id":{"isi":["000418371407018"]},"publist_id":"6525","author":[{"first_name":"Paul","id":"446560C6-F248-11E8-B48F-1D18A9856A87","full_name":"Swoboda, Paul","last_name":"Swoboda"},{"first_name":"Carsten","last_name":"Rother","full_name":"Rother, Carsten"},{"full_name":"Abu Alhaija, Carsten","last_name":"Abu Alhaija","first_name":"Carsten"},{"first_name":"Dagmar","full_name":"Kainmueller, Dagmar","last_name":"Kainmueller"},{"first_name":"Bogdan","full_name":"Savchynskyy, Bogdan","last_name":"Savchynskyy"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"ista":"Swoboda P, Rother C, Abu Alhaija C, Kainmueller D, Savchynskyy B. 2017. A study of lagrangean decompositions and dual ascent solvers for graph matching. CVPR: Computer Vision and Pattern Recognition vol. 2017, 7062–7071.","chicago":"Swoboda, Paul, Carsten Rother, Carsten Abu Alhaija, Dagmar Kainmueller, and Bogdan Savchynskyy. “A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching,” 2017:7062–71. IEEE, 2017. https://doi.org/10.1109/CVPR.2017.747.","short":"P. Swoboda, C. Rother, C. Abu Alhaija, D. Kainmueller, B. Savchynskyy, in:, IEEE, 2017, pp. 7062–7071.","ieee":"P. Swoboda, C. Rother, C. Abu Alhaija, D. Kainmueller, and B. Savchynskyy, “A study of lagrangean decompositions and dual ascent solvers for graph matching,” presented at the CVPR: Computer Vision and Pattern Recognition, Honolulu, HA, United States, 2017, vol. 2017, pp. 7062–7071.","ama":"Swoboda P, Rother C, Abu Alhaija C, Kainmueller D, Savchynskyy B. A study of lagrangean decompositions and dual ascent solvers for graph matching. In: Vol 2017. IEEE; 2017:7062-7071. doi:10.1109/CVPR.2017.747","apa":"Swoboda, P., Rother, C., Abu Alhaija, C., Kainmueller, D., & Savchynskyy, B. (2017). A study of lagrangean decompositions and dual ascent solvers for graph matching (Vol. 2017, pp. 7062–7071). Presented at the CVPR: Computer Vision and Pattern Recognition, Honolulu, HA, United States: IEEE. https://doi.org/10.1109/CVPR.2017.747","mla":"Swoboda, Paul, et al. A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching. Vol. 2017, IEEE, 2017, pp. 7062–71, doi:10.1109/CVPR.2017.747."},"intvolume":" 2017","month":"01","scopus_import":"1","oa_version":"Submitted Version","abstract":[{"text":"We study the quadratic assignment problem, in computer vision also known as graph matching. Two leading solvers for this problem optimize the Lagrange decomposition duals with sub-gradient and dual ascent (also known as message passing) updates. We explore this direction further and propose several additional Lagrangean relaxations of the graph matching problem along with corresponding algorithms, which are all based on a common dual ascent framework. Our extensive empirical evaluation gives several theoretical insights and suggests a new state-of-the-art anytime solver for the considered problem. Our improvement over state-of-the-art is particularly visible on a new dataset with large-scale sparse problem instances containing more than 500 graph nodes each.","lang":"eng"}],"ec_funded":1,"volume":2017,"language":[{"iso":"eng"}],"file":[{"creator":"dernst","file_size":944332,"date_updated":"2020-07-14T12:48:15Z","file_name":"2017_CVPR_Swoboda2.pdf","date_created":"2019-01-18T12:49:38Z","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_id":"5848","checksum":"e38a2740daad1ea178465843b5072906"}],"publication_status":"published","publication_identifier":{"isbn":["978-153860457-1"]},"status":"public","conference":{"name":"CVPR: Computer Vision and Pattern Recognition","location":"Honolulu, HA, United States","end_date":"2017-07-26","start_date":"2017-07-21"},"type":"conference","_id":"916","department":[{"_id":"VlKo"}],"file_date_updated":"2020-07-14T12:48:15Z","ddc":["000"],"date_updated":"2023-09-26T15:41:40Z"},{"oa_version":"Submitted Version","abstract":[{"lang":"eng","text":"We propose a dual decomposition and linear program relaxation of the NP-hard minimum cost multicut problem. Unlike other polyhedral relaxations of the multicut polytope, it is amenable to efficient optimization by message passing. Like other polyhedral relaxations, it can be tightened efficiently by cutting planes. We define an algorithm that alternates between message passing and efficient separation of cycle- and odd-wheel inequalities. This algorithm is more efficient than state-of-the-art algorithms based on linear programming, including algorithms written in the framework of leading commercial software, as we show in experiments with large instances of the problem from applications in computer vision, biomedical image analysis and data mining."}],"month":"07","intvolume":" 2017","scopus_import":"1","file":[{"date_updated":"2020-07-14T12:48:15Z","file_size":883264,"creator":"dernst","date_created":"2019-01-18T12:52:46Z","file_name":"Swoboda_A_Message_Passing_CVPR_2017_paper.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_id":"5849","checksum":"7e51dacefa693574581a32da3eff63dc"}],"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["978-153860457-1"]},"publication_status":"published","volume":2017,"ec_funded":1,"_id":"915","status":"public","type":"conference","conference":{"location":"Honolulu, HA, United States","end_date":"2017-07-26","start_date":"2017-07-21","name":"CVPR: Computer Vision and Pattern Recognition"},"ddc":["000"],"date_updated":"2023-09-26T15:43:27Z","file_date_updated":"2020-07-14T12:48:15Z","department":[{"_id":"VlKo"}],"publisher":"IEEE","quality_controlled":"1","oa":1,"day":"01","isi":1,"has_accepted_license":"1","year":"2017","date_published":"2017-07-01T00:00:00Z","doi":"10.1109/CVPR.2017.530","date_created":"2018-12-11T11:49:11Z","page":"4990-4999","project":[{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"ieee":"P. Swoboda and B. Andres, “A message passing algorithm for the minimum cost multicut problem,” presented at the CVPR: Computer Vision and Pattern Recognition, Honolulu, HA, United States, 2017, vol. 2017, pp. 4990–4999.","short":"P. Swoboda, B. Andres, in:, IEEE, 2017, pp. 4990–4999.","apa":"Swoboda, P., & Andres, B. (2017). A message passing algorithm for the minimum cost multicut problem (Vol. 2017, pp. 4990–4999). Presented at the CVPR: Computer Vision and Pattern Recognition, Honolulu, HA, United States: IEEE. https://doi.org/10.1109/CVPR.2017.530","ama":"Swoboda P, Andres B. A message passing algorithm for the minimum cost multicut problem. In: Vol 2017. IEEE; 2017:4990-4999. doi:10.1109/CVPR.2017.530","mla":"Swoboda, Paul, and Bjoern Andres. A Message Passing Algorithm for the Minimum Cost Multicut Problem. Vol. 2017, IEEE, 2017, pp. 4990–99, doi:10.1109/CVPR.2017.530.","ista":"Swoboda P, Andres B. 2017. A message passing algorithm for the minimum cost multicut problem. CVPR: Computer Vision and Pattern Recognition vol. 2017, 4990–4999.","chicago":"Swoboda, Paul, and Bjoern Andres. “A Message Passing Algorithm for the Minimum Cost Multicut Problem,” 2017:4990–99. IEEE, 2017. https://doi.org/10.1109/CVPR.2017.530."},"title":"A message passing algorithm for the minimum cost multicut problem","publist_id":"6526","author":[{"last_name":"Swoboda","full_name":"Swoboda, Paul","first_name":"Paul","id":"446560C6-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Bjoern","full_name":"Andres, Bjoern","last_name":"Andres"}],"article_processing_charge":"No","external_id":{"isi":["000418371405009"]}},{"project":[{"name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160","call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425"}],"citation":{"ista":"Swoboda P, Kuske J, Savchynskyy B. 2017. A dual ascent framework for Lagrangean decomposition of combinatorial problems. CVPR: Computer Vision and Pattern Recognition vol. 2017, 4950–4960.","chicago":"Swoboda, Paul, Jan Kuske, and Bogdan Savchynskyy. “A Dual Ascent Framework for Lagrangean Decomposition of Combinatorial Problems,” 2017:4950–60. IEEE, 2017. https://doi.org/10.1109/CVPR.2017.526.","short":"P. Swoboda, J. Kuske, B. Savchynskyy, in:, IEEE, 2017, pp. 4950–4960.","ieee":"P. Swoboda, J. Kuske, and B. Savchynskyy, “A dual ascent framework for Lagrangean decomposition of combinatorial problems,” presented at the CVPR: Computer Vision and Pattern Recognition, Honolulu, HA, United States, 2017, vol. 2017, pp. 4950–4960.","apa":"Swoboda, P., Kuske, J., & Savchynskyy, B. (2017). A dual ascent framework for Lagrangean decomposition of combinatorial problems (Vol. 2017, pp. 4950–4960). Presented at the CVPR: Computer Vision and Pattern Recognition, Honolulu, HA, United States: IEEE. https://doi.org/10.1109/CVPR.2017.526","ama":"Swoboda P, Kuske J, Savchynskyy B. A dual ascent framework for Lagrangean decomposition of combinatorial problems. In: Vol 2017. IEEE; 2017:4950-4960. doi:10.1109/CVPR.2017.526","mla":"Swoboda, Paul, et al. A Dual Ascent Framework for Lagrangean Decomposition of Combinatorial Problems. Vol. 2017, IEEE, 2017, pp. 4950–60, doi:10.1109/CVPR.2017.526."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","article_processing_charge":"No","external_id":{"isi":["000418371405005"]},"publist_id":"6524","author":[{"first_name":"Paul","id":"446560C6-F248-11E8-B48F-1D18A9856A87","last_name":"Swoboda","full_name":"Swoboda, Paul"},{"last_name":"Kuske","full_name":"Kuske, Jan","first_name":"Jan"},{"full_name":"Savchynskyy, Bogdan","last_name":"Savchynskyy","first_name":"Bogdan"}],"title":"A dual ascent framework for Lagrangean decomposition of combinatorial problems","oa":1,"publisher":"IEEE","quality_controlled":"1","year":"2017","isi":1,"has_accepted_license":"1","day":"01","page":"4950-4960","date_created":"2018-12-11T11:49:11Z","date_published":"2017-07-01T00:00:00Z","doi":"10.1109/CVPR.2017.526","_id":"917","conference":{"name":"CVPR: Computer Vision and Pattern Recognition","end_date":"2017-07-26","location":"Honolulu, HA, United States","start_date":"2017-07-21"},"type":"conference","status":"public","date_updated":"2023-09-26T15:41:11Z","ddc":["000"],"department":[{"_id":"VlKo"}],"file_date_updated":"2020-07-14T12:48:15Z","abstract":[{"lang":"eng","text":"We propose a general dual ascent framework for Lagrangean decomposition of combinatorial problems. Although methods of this type have shown their efficiency for a number of problems, so far there was no general algorithm applicable to multiple problem types. In this work, we propose such a general algorithm. It depends on several parameters, which can be used to optimize its performance in each particular setting. We demonstrate efficacy of our method on graph matching and multicut problems, where it outperforms state-of-the-art solvers including those based on subgradient optimization and off-the-shelf linear programming solvers."}],"oa_version":"Submitted Version","scopus_import":"1","intvolume":" 2017","month":"07","publication_status":"published","publication_identifier":{"isbn":["978-153860457-1"]},"language":[{"iso":"eng"}],"file":[{"date_created":"2019-01-18T12:45:55Z","file_name":"2017_CVPR_Swoboda.pdf","date_updated":"2020-07-14T12:48:15Z","file_size":898652,"creator":"dernst","checksum":"72fd291046bd8e5717961bd68f6b6f03","file_id":"5847","content_type":"application/pdf","access_level":"open_access","relation":"main_file"}],"ec_funded":1,"volume":2017},{"date_published":"2017-12-27T00:00:00Z","date_created":"2018-12-11T11:45:33Z","page":"228-249","day":"27","publication":"Proceedings of the 31st Conference On Learning Theory","has_accepted_license":"1","year":"2017","quality_controlled":"1","publisher":"ML Research Press","oa":1,"title":"A faster approximation algorithm for the Gibbs partition function","author":[{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov"}],"publist_id":"7628","article_processing_charge":"No","external_id":{"arxiv":["1608.04223"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ama":"Kolmogorov V. A faster approximation algorithm for the Gibbs partition function. In: Proceedings of the 31st Conference On Learning Theory. Vol 75. ML Research Press; 2017:228-249.","apa":"Kolmogorov, V. (2017). A faster approximation algorithm for the Gibbs partition function. In Proceedings of the 31st Conference On Learning Theory (Vol. 75, pp. 228–249). ML Research Press.","ieee":"V. Kolmogorov, “A faster approximation algorithm for the Gibbs partition function,” in Proceedings of the 31st Conference On Learning Theory, 2017, vol. 75, pp. 228–249.","short":"V. Kolmogorov, in:, Proceedings of the 31st Conference On Learning Theory, ML Research Press, 2017, pp. 228–249.","mla":"Kolmogorov, Vladimir. “A Faster Approximation Algorithm for the Gibbs Partition Function.” Proceedings of the 31st Conference On Learning Theory, vol. 75, ML Research Press, 2017, pp. 228–49.","ista":"Kolmogorov V. 2017. A faster approximation algorithm for the Gibbs partition function. Proceedings of the 31st Conference On Learning Theory. COLT: Annual Conference on Learning Theory vol. 75, 228–249.","chicago":"Kolmogorov, Vladimir. “A Faster Approximation Algorithm for the Gibbs Partition Function.” In Proceedings of the 31st Conference On Learning Theory, 75:228–49. ML Research Press, 2017."},"project":[{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"volume":75,"ec_funded":1,"file":[{"file_name":"2018_PMLR_Kolmogorov.pdf","date_created":"2020-05-12T09:23:27Z","creator":"dernst","file_size":408974,"date_updated":"2020-07-14T12:45:45Z","file_id":"7820","checksum":"89db06a0e8083524449cb59b56bf4e5b","relation":"main_file","access_level":"open_access","content_type":"application/pdf"}],"language":[{"iso":"eng"}],"publication_status":"published","month":"12","intvolume":" 75","oa_version":"Published Version","abstract":[{"text":"We consider the problem of estimating the partition function Z(β)=∑xexp(−β(H(x)) of a Gibbs distribution with a Hamilton H(⋅), or more precisely the logarithm of the ratio q=lnZ(0)/Z(β). It has been recently shown how to approximate q with high probability assuming the existence of an oracle that produces samples from the Gibbs distribution for a given parameter value in [0,β]. The current best known approach due to Huber [9] uses O(qlnn⋅[lnq+lnlnn+ε−2]) oracle calls on average where ε is the desired accuracy of approximation and H(⋅) is assumed to lie in {0}∪[1,n]. We improve the complexity to O(qlnn⋅ε−2) oracle calls. We also show that the same complexity can be achieved if exact oracles are replaced with approximate sampling oracles that are within O(ε2qlnn) variation distance from exact oracles. Finally, we prove a lower bound of Ω(q⋅ε−2) oracle calls under a natural model of computation.","lang":"eng"}],"department":[{"_id":"VlKo"}],"file_date_updated":"2020-07-14T12:45:45Z","ddc":["510"],"date_updated":"2023-10-17T12:32:13Z","status":"public","type":"conference","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"conference":{"name":"COLT: Annual Conference on Learning Theory ","end_date":"2018-07-09","start_date":"2018-07-06"},"_id":"274"},{"has_accepted_license":"1","year":"2017","datarep_id":"57","file":[{"creator":"system","date_updated":"2020-07-14T12:47:03Z","file_size":327042819,"date_created":"2018-12-12T13:02:54Z","file_name":"IST-2017-57-v1+1_wormMatchingProblems.zip","access_level":"open_access","relation":"main_file","content_type":"application/zip","file_id":"5614","checksum":"3dc3e1306a66028a34181ebef2923139"}],"day":"13","doi":"10.15479/AT:ISTA:57","date_published":"2017-02-13T00:00:00Z","date_created":"2018-12-12T12:31:32Z","license":"https://creativecommons.org/publicdomain/zero/1.0/","abstract":[{"lang":"eng","text":"Graph matching problems as described in \"Active Graph Matching for Automatic Joint Segmentation and Annotation of C. Elegans.\" by Kainmueller, Dagmar and Jug, Florian and Rother, Carsten and Myers, Gene, MICCAI 2014. Problems are in OpenGM2 hdf5 format (see http://hciweb2.iwr.uni-heidelberg.de/opengm/) and a custom text format used by the feature matching solver described in \"Feature Correspondence via Graph Matching: Models and Global Optimization.\" by Lorenzo Torresani, Vladimir Kolmogorov and Carsten Rother, ECCV 2008, code at http://pub.ist.ac.at/~vnk/software/GraphMatching-v1.02.src.zip. "}],"oa_version":"Published Version","acknowledgement":"We thank Vladimir Kolmogorov and Stephan Saalfeld forinspiring discussions.","publisher":"Institute of Science and Technology Austria","oa":1,"month":"02","citation":{"chicago":"Kainmueller, Dagmar, Florian Jug, Carsten Rother, and Gene Meyers. “Graph Matching Problems for Annotating C. Elegans.” Institute of Science and Technology Austria, 2017. https://doi.org/10.15479/AT:ISTA:57.","ista":"Kainmueller D, Jug F, Rother C, Meyers G. 2017. Graph matching problems for annotating C. Elegans, Institute of Science and Technology Austria, 10.15479/AT:ISTA:57.","mla":"Kainmueller, Dagmar, et al. Graph Matching Problems for Annotating C. Elegans. Institute of Science and Technology Austria, 2017, doi:10.15479/AT:ISTA:57.","short":"D. Kainmueller, F. Jug, C. Rother, G. Meyers, (2017).","ieee":"D. Kainmueller, F. Jug, C. Rother, and G. Meyers, “Graph matching problems for annotating C. Elegans.” Institute of Science and Technology Austria, 2017.","apa":"Kainmueller, D., Jug, F., Rother, C., & Meyers, G. (2017). Graph matching problems for annotating C. Elegans. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:57","ama":"Kainmueller D, Jug F, Rother C, Meyers G. Graph matching problems for annotating C. Elegans. 2017. doi:10.15479/AT:ISTA:57"},"date_updated":"2024-02-21T13:46:31Z","ddc":["000"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Dagmar","full_name":"Kainmueller, Dagmar","last_name":"Kainmueller"},{"first_name":"Florian","last_name":"Jug","full_name":"Jug, Florian"},{"first_name":"Carsten","last_name":"Rother","full_name":"Rother, Carsten"},{"first_name":"Gene","full_name":"Meyers, Gene","last_name":"Meyers"}],"article_processing_charge":"No","file_date_updated":"2020-07-14T12:47:03Z","title":"Graph matching problems for annotating C. Elegans","department":[{"_id":"VlKo"}],"_id":"5561","type":"research_data","tmp":{"image":"/images/cc_0.png","legal_code_url":"https://creativecommons.org/publicdomain/zero/1.0/legalcode","name":"Creative Commons Public Domain Dedication (CC0 1.0)","short":"CC0 (1.0)"},"status":"public","keyword":["graph matching","feature matching","QAP","MAP-inference"]}]