{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T08:24:20Z","timestamp":1774599860177,"version":"3.50.1"},"reference-count":19,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"7","license":[{"start":{"date-parts":[[2017,7,1]],"date-time":"2017-07-01T00:00:00Z","timestamp":1498867200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"}],"funder":[{"DOI":"10.13039\/501100001823","name":"Ministerstvo \u0160kolstv\u00ed, Ml\u00e1de\u017ee a T\u011blov\u00fdchovy","doi-asserted-by":"publisher","award":["ERC-CZ grant LL1303"],"award-info":[{"award-number":["ERC-CZ grant LL1303"]}],"id":[{"id":"10.13039\/501100001823","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Pattern Anal. Mach. Intell."],"published-print":{"date-parts":[[2017,7,1]]},"DOI":"10.1109\/tpami.2016.2582165","type":"journal-article","created":{"date-parts":[[2016,6,20]],"date-time":"2016-06-20T16:30:36Z","timestamp":1466440236000},"page":"1469-1475","source":"Crossref","is-referenced-by-count":6,"title":["LP Relaxation of the Potts Labeling Problem Is as Hard as Any Linear Program"],"prefix":"10.1109","volume":"39","author":[{"given":"Daniel","family":"Prusa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomas","family":"Werner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"263","reference":[{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00336-5"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2007.383203"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1109\/34.969114"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585268"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101396937"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1137\/06065430X"},{"key":"ref16","first-page":"109","article-title":"Rounding-based moves for metric labeling","author":"kumar","year":"0","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref17","first-page":"48","article-title":"An improved approximation algorithm for multiway cut","author":"c?linescu","year":"0","journal-title":"Proc 30th Annu ACM Symp Theory Comput"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1137\/040610623"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01844844"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1561\/2200000001"},{"key":"ref3","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-33974-5","author":"\u017eivn\u00fd","year":"2012","journal-title":"On the Complexity of Constraint Satisfaction Problems"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.1036"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01070399"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1137\/130945648"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(98)00043-1"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-015-0809-x"},{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.70844"},{"key":"ref9","doi-asserted-by":"crossref","first-page":"898","DOI":"10.1109\/TPAMI.2014.2353626","article-title":"Universality of the local marginal polytope","volume":"37","author":"pr","year":"2015","journal-title":"IEEE Trans Pattern Anal Mach Intell"}],"container-title":["IEEE Transactions on Pattern Analysis and Machine Intelligence"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/34\/7938536\/07494684.pdf?arnumber=7494684","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,12]],"date-time":"2022-01-12T11:40:28Z","timestamp":1641987628000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/7494684\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,1]]},"references-count":19,"journal-issue":{"issue":"7"},"URL":"https:\/\/doi.org\/10.1109\/tpami.2016.2582165","relation":{},"ISSN":["0162-8828","2160-9292","1939-3539"],"issn-type":[{"value":"0162-8828","type":"print"},{"value":"2160-9292","type":"electronic"},{"value":"1939-3539","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,7,1]]}}}