{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T02:53:35Z","timestamp":1775184815267,"version":"3.50.1"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,11,22]],"date-time":"2021-11-22T00:00:00Z","timestamp":1637539200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council"},{"name":"European Union\u2019s Horizon 2020","award":["681988"],"award-info":[{"award-number":["681988"]}]},{"name":"DFG Graduiertenkolleg 1763"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2022,1,31]]},"abstract":"<jats:p>Valued constraint satisfaction problems (VCSPs) are a large class of combinatorial optimisation problems. The computational complexity of VCSPs depends on the set of allowed cost functions in the input. Recently, the computational complexity of all VCSPs for finite sets of cost functions over finite domains has been classified. Many natural optimisation problems, however, cannot be formulated as VCSPs over a finite domain. We initiate the systematic investigation of the complexity of infinite-domain VCSPs with piecewise linear homogeneous cost functions. Such VCSPs can be solved in polynomial time if the cost functions are improved by fully symmetric fractional operations of all arities. We show this by reducing the problem to a finite-domain VCSP which can be solved using the basic linear program relaxation. It follows that VCSPs for submodular PLH cost functions can be solved in polynomial time; in fact, we show that submodular PLH functions form a maximally tractable class of PLH cost functions.<\/jats:p>","DOI":"10.1145\/3488721","type":"journal-article","created":{"date-parts":[[2021,11,22]],"date-time":"2021-11-22T17:43:55Z","timestamp":1637603035000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation"],"prefix":"10.1145","volume":"23","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Dresden, Dresden (Germany)"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcello","family":"Mamino","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Pisa, Pisa (Italy)"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Caterina","family":"Viola","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Dresden, Oxford (United Kingdom)"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,11,22]]},"reference":[{"key":"e_1_3_1_2_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033116.57574.95"},{"key":"e_1_3_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_16"},{"key":"e_1_3_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2528933"},{"key":"e_1_3_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-017-9762-0"},{"key":"e_1_3_1_6_1","first-page":"12:1\u201312:22","volume-title":"Proceedings of the 27th EACSL Annual Conference on Computer Science Logic (CSL\u201918)","author":"Bodirsky Manuel","year":"2018","unstructured":"Manuel Bodirsky, Marcello Mamino, and Caterina Viola. 2018. Submodular functions and valued constraint satisfaction problems over infinite domains. In Proceedings of the 27th EACSL Annual Conference on Computer Science Logic (CSL\u201918). 12:1\u201312:22."},{"key":"e_1_3_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/993483"},{"key":"e_1_3_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.37"},{"key":"e_1_3_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1163940.1644558"},{"key":"e_1_3_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204006"},{"key":"e_1_3_1_11_1","volume-title":"Submodular Functions and Optimization","author":"Fujishige Satoru","year":"2005","unstructured":"Satoru Fujishige. 2005. Submodular Functions and Optimization (2nd ed.). North-Holland, Amsterdam."},{"key":"e_1_3_1_12_1","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"Gr\u00f6tschel M.","year":"1994","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, and L. Schrijver. 1994. Geometric Algorithms and Combinatorial Optimization (2nd ed.). Springer, Heidelberg."},{"key":"e_1_3_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/262326"},{"key":"e_1_3_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02418571"},{"key":"e_1_3_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/2041160.2041197"},{"key":"e_1_3_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.80"},{"key":"e_1_3_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/130945648"},{"key":"e_1_3_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_69"},{"key":"e_1_3_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536512"},{"key":"e_1_3_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCD.2012.6378643"},{"key":"e_1_3_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.25"},{"key":"e_1_3_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488697"},{"key":"e_1_3_1_23_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511525919"},{"key":"e_1_3_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.38"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3488721","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3488721","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:28Z","timestamp":1750193308000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3488721"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,22]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1,31]]}},"alternative-id":["10.1145\/3488721"],"URL":"https:\/\/doi.org\/10.1145\/3488721","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,22]]},"assertion":[{"value":"2019-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}