乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,27]],"date-time":"2024-08-27T13:05:44Z","timestamp":1724763944688},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"name":"ERC","award":["714532"]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2021,7,31]]},"abstract":"Convex relaxations have been instrumental in solvability of constraint satisfaction problems (CSPs), as well as in the three different generalisations of CSPs: valued CSPs, infinite-domain CSPs, and most recently promise CSPs. In this work, we extend an existing tractability result to the three generalisations of CSPs combined: We give a sufficient condition for the combined basic linear programming and affine integer programming relaxation for exact solvability of promise valued CSPs over infinite-domains. This extends a result of Brakensiek and Guruswami\u00a0(SODA\u201920) for promise (non-valued) CSPs (on finite domains).<\/jats:p>","DOI":"10.1145\/3458041","type":"journal-article","created":{"date-parts":[[2021,7,16]],"date-time":"2021-07-16T05:26:33Z","timestamp":1626413193000},"page":"1-23","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["The Combined Basic LP and Affine IP Relaxation for Promise VCSPs on Infinite Domains"],"prefix":"10.1145","volume":"17","author":[{"given":"Caterina","family":"Viola","sequence":"first","affiliation":[{"name":"University of Oxford, United Kingdom"}]},{"given":"Stanislav","family":"\u017divn\u00fd","sequence":"additional","affiliation":[{"name":"University of Oxford, United Kingdom"}]}],"member":"320","published-online":{"date-parts":[[2021,7,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmaa.2007.02.016"},{"key":"e_1_2_1_2_1","first-page":"405","article-title":"Konvexe Funktionen und Induktion bei Ungleichungen zwischen Mittelverten. Akad. Wiss. Math.-Natur. Kl. Abh","volume":"109","author":"Aumann G","year":"1933","unstructured":"G Aumann . 1933 . Konvexe Funktionen und Induktion bei Ungleichungen zwischen Mittelverten. Akad. Wiss. Math.-Natur. Kl. Abh ., Math. Ann 109 (1933), 405 \u2013 413 . Retrieved from https:\/\/www.zobodat.at\/pdf\/Sitz-Ber-Akad-Muenchen-math-Kl_1933_0403-0415.pdf. G Aumann. 1933. Konvexe Funktionen und Induktion bei Ungleichungen zwischen Mittelverten. Akad. Wiss. Math.-Natur. Kl. Abh., Math. Ann 109 (1933), 405\u2013413. Retrieved from https:\/\/www.zobodat.at\/pdf\/Sitz-Ber-Akad-Muenchen-math-Kl_1933_0403-0415.pdf.","journal-title":"Math. Ann"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2462896.2462897"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033116.57574.95"},{"key":"e_1_2_1_5_1","article-title":"Algebraic approach to promise constraint satisfaction","volume":"10","author":"Barto Libor","year":"2019","unstructured":"Libor Barto , Jakub Bul\u00edn , Andrei Krokhin , and Jakub Opr\u0161al . 2019 . Algebraic approach to promise constraint satisfaction . Journal of the ACM. DOI:DOI : 10 .1145\/3457606 10.1145\/3457606 Libor Barto, Jakub Bul\u00edn, Andrei Krokhin, and Jakub Opr\u0161al. 2019. Algebraic approach to promise constraint satisfaction. Journal of the ACM. DOI:DOI:10.1145\/3457606","journal-title":"Journal of the ACM. DOI:DOI"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/130915479"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1216213"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_16"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3105907"},{"key":"e_1_2_1_10_1","volume-title":"Essential convexity and complexity of semi-algebraic constraints. Log. Meth. Comput. Sci. 8, 4","author":"Bodirsky Manuel","year":"2012","unstructured":"Manuel Bodirsky , Peter Jonsson , and Timo Von Oertzen . 2012. Essential convexity and complexity of semi-algebraic constraints. Log. Meth. Comput. Sci. 8, 4 ( 2012 ). DOI:DOI:https:\/\/doi.org\/10.2168\/LMCS-8(4:5)2012 Manuel Bodirsky, Peter Jonsson, and Timo Von Oertzen. 2012. Essential convexity and complexity of semi-algebraic constraints. Log. Meth. Comput. Sci. 8, 4 (2012). DOI:DOI:https:\/\/doi.org\/10.2168\/LMCS-8(4:5)2012"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667058"},{"key":"e_1_2_1_12_1","unstructured":"Manuel Bodirsky Marcello Mamino and Caterina Viola. 2019. Piecewise linear valued CSPs solvable by linear programming relaxation. (2019). arXiv:1912.09298 Manuel Bodirsky Marcello Mamino and Caterina Viola. 2019. Piecewise linear valued CSPs solvable by linear programming relaxation. (2019). arXiv:1912.09298"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3154832"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1082974"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764899"},{"key":"e_1_2_1_16_1","volume-title":"Boyd and Lieven Vandenberghe","author":"Stephen","year":"2004","unstructured":"Stephen P. Boyd and Lieven Vandenberghe . 2004 . Convex Optimization. Cambridge University Press . Retrieved from https:\/\/web.stanford.edu\/ boyd\/cvxbook\/bv_cvxbook.pdf. Stephen P. Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press. Retrieved from https:\/\/web.stanford.edu\/ boyd\/cvxbook\/bv_cvxbook.pdf."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.117"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.28"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.18"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1312745"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.37"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316300"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2873054"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2811255"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211057"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/130906398"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1163932"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2540090"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_2_1_31_1","first-page":"1","article-title":"Dichotomy for symmetric Boolean PCSPs. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP\u201919) (LIPIcs), Vol. 132","volume":"57","author":"Ficak Miron","year":"2019","unstructured":"Miron Ficak , Marcin Kozik , Miroslav Ol\u0161\u00e1k , and Szymon Stankiewicz . 2019 . Dichotomy for symmetric Boolean PCSPs. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP\u201919) (LIPIcs), Vol. 132 . Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik , 57 : 1 \u2013 57 :12. DOI:DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.57 Miron Ficak, Marcin Kozik, Miroslav Ol\u0161\u00e1k, and Szymon Stankiewicz. 2019. Dichotomy for symmetric Boolean PCSPs. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP\u201919) (LIPIcs), Vol. 132. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 57:1\u201357:12. DOI:DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.57","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2018.v014a010"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_2_1_34_1","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"Gr\u00f6tschel Martin","unstructured":"Martin Gr\u00f6tschel , L\u00e1szl\u00f3 Lov\u00e1sz , and Alexander Schrijver . 1993. Geometric Algorithms and Combinatorial Optimization . Vol. 2 . Springer-Verlag Berlin . DOI:DOI:https:\/\/doi.org\/10.1007\/978-3-642-78240-4 Martin Gr\u00f6tschel, L\u00e1szl\u00f3 Lov\u00e1sz, and Alexander Schrijver. 1993. Geometric Algorithms and Combinatorial Optimization. Vol. 2. Springer-Verlag Berlin. DOI:DOI:https:\/\/doi.org\/10.1007\/978-3-642-78240-4"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1631\/jzus.C1010311"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.03.002"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208040"},{"key":"e_1_2_1_38_1","unstructured":"Alexander Kazda. 2021. Minion homomorphisms give reductions between promise valued CSPs. (2021). In preparation. Alexander Kazda. 2021. Minion homomorphisms give reductions between promise valued CSPs. (2021). In preparation."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1091836"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/130945648"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055438"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90125-6"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_69"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090274"},{"key":"e_1_2_1_45_1","volume-title":"S\u00f3s","author":"Laczkovich Mikl\u00f3s","year":"2017","unstructured":"Mikl\u00f3s Laczkovich and Vera T . S\u00f3s . 2017 . Real Analysis : Series, Functions of Several Variables, and Applications. Vol. 3 . Springer , New York, NY. DOI:DOI:https:\/\/doi.org\/10.1007\/978-1-4939-7369-9 Mikl\u00f3s Laczkovich and Vera T. S\u00f3s. 2017. Real Analysis: Series, Functions of Several Variables, and Applications. Vol. 3. Springer, New York, NY. DOI:DOI:https:\/\/doi.org\/10.1007\/978-1-4939-7369-9"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746599"},{"key":"e_1_2_1_47_1","volume-title":"Elementary Probability Theory","author":"Lo\u00e8ve M.","unstructured":"M. Lo\u00e8ve . 1977. Elementary Probability Theory . Springer , New York, NY , 1\u201352. DOI:DOI:https:\/\/doi.org\/10.1007\/978-1-4684-9464-8_1 M. Lo\u00e8ve. 1977. Elementary Probability Theory. Springer, New York, NY, 1\u201352. DOI:DOI:https:\/\/doi.org\/10.1007\/978-1-4684-9464-8_1"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374414"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41947-8_4"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.25"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2974019"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1079245"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3201777"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536457"},{"key":"e_1_2_1_57_1","volume-title":"Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201920)","volume":"170","author":"Viola Caterina","year":"2020","unstructured":"Caterina Viola and Stanislav \u017divn\u00fd . 2020 . The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains . In Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201920) , Vol. 170 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 82:1\u201382:15. DOI:DOI:https:\/\/doi.org\/10.4230\/LIPIcs.MFCS. 2020.85 Caterina Viola and Stanislav \u017divn\u00fd. 2020. The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains. In Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201920), Vol. 170. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 82:1\u201382:15. DOI:DOI:https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2020.85"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3402029"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3458041","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T20:48:13Z","timestamp":1672606093000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3458041"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,15]]},"references-count":57,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,7,31]]}},"alternative-id":["10.1145\/3458041"],"URL":"https:\/\/doi.org\/10.1145\/3458041","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,15]]},"assertion":[{"value":"2020-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}