{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T07:37:08Z","timestamp":1743061028307,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476710"},{"type":"electronic","value":"9783662476727"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_86","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T10:07:39Z","timestamp":1434708459000},"page":"1058-1069","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Sherali-Adams Relaxations for Valued CSPs"],"prefix":"10.1007","author":[{"given":"Johan","family":"Thapper","sequence":"first","affiliation":[]},{"given":"Stanislav","family":"\u017divn\u00fd","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"86_CR1","doi-asserted-by":"crossref","unstructured":"Barto, L.: The collapse of the bounded width hierarchy. Journal of Logic and Computation (2014)","DOI":"10.1093\/logcom\/exu070"},{"key":"86_CR2","doi-asserted-by":"crossref","unstructured":"Barto, L., Kozik, M.: Robust Satisfiability of Constraint Satisfaction Problems. In: Proc. STOC 2012, pp. 931\u2013940. ACM (2012)","DOI":"10.1145\/2213977.2214061"},{"key":"86_CR3","doi-asserted-by":"crossref","unstructured":"Barto, L., Kozik, M.: Constraint Satisfaction Problems Solvable by Local Consistency Methods. Journal of the ACM 61(1), Article No. 3 (2014)","DOI":"10.1145\/2556646"},{"key":"86_CR4","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/j.jalgebra.2004.07.044","volume":"298","author":"A Bulatov","year":"2006","unstructured":"Bulatov, A.: Combinatorial problems raised from 2-semilattices. Journal of Algebra 298, 321\u2013339 (2006)","journal-title":"Journal of Algebra"},{"issue":"3","key":"86_CR5","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1137\/S0097539700376676","volume":"34","author":"A Bulatov","year":"2005","unstructured":"Bulatov, A., Krokhin, A., Jeavons, P.: Classifying the Complexity of Constraints using Finite Algebras. SIAM Journal on Computing 34(3), 720\u2013742 (2005)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"86_CR6","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1137\/S0895480101396937","volume":"18","author":"C Chekuri","year":"2004","unstructured":"Chekuri, C., Khanna, S., Naor, J., Zosin, L.: A linear programming formulation and approximation algorithms for the metric labeling problem. SIAM J. on Discrete Mathematics 18(3), 608\u2013625 (2004)","journal-title":"SIAM J. on Discrete Mathematics"},{"issue":"1\u20133","key":"86_CR7","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.tcs.2008.03.015","volume":"401","author":"DA Cohen","year":"2008","unstructured":"Cohen, D.A., Cooper, M.C., Jeavons, P.G.: Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms. Theoretical Computer Science 401(1\u20133), 36\u201351 (2008)","journal-title":"Theoretical Computer Science"},{"key":"86_CR8","doi-asserted-by":"publisher","first-page":"983","DOI":"10.1016\/j.artint.2006.04.002","volume":"170","author":"DA Cohen","year":"2006","unstructured":"Cohen, D.A., Cooper, M.C., Jeavons, P.G., Krokhin, A.A.: The Complexity of Soft Constraint Satisfaction. Artif. Intell. 170, 983\u20131016 (2006)","journal-title":"Artif. Intell."},{"key":"86_CR9","doi-asserted-by":"crossref","unstructured":"Dalmau, V., Krokhin, A., Manokaran, R.: Towards a characterization of constant-factor approximable Min CSPs. In: Proc. SODA 2015 (2015)","DOI":"10.1137\/1.9781611973730.58"},{"key":"86_CR10","doi-asserted-by":"crossref","unstructured":"Dalmau, V., Krokhin, A.A.: Robust Satisfiability for CSPs: Hardness and Algorithmic Results. ACM ToCT 5(4), Article No. 15 (2013)","DOI":"10.1145\/2540090"},{"key":"86_CR11","unstructured":"de la Vega, W. F., Kenyon-Mathieu, C.: Linear programming relaxations of maxcut. In: Proc. SODA 2007, pp. 53\u201361. SIAM (2007)"},{"key":"86_CR12","doi-asserted-by":"crossref","unstructured":"Ene, A., Vondr\u00e1k, J., Wu, Y.: Local distribution and the symmetry gap: Approximability of multiway partitioning problems. In: SODA 2013, pp. 306\u2013325 (2013)","DOI":"10.1137\/1.9781611973105.23"},{"issue":"1","key":"86_CR13","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T Feder","year":"1998","unstructured":"Feder, T., Vardi, M.Y.: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory. SIAM Journal on Computing 28(1), 57\u2013104 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"86_CR14","doi-asserted-by":"crossref","unstructured":"Fulla, P., \u017divn\u00fd, S.: A Galois Connection for Valued Constraint Lan-guages of Infinite Size. In: Proc. ICALP 2015. Springer (2015)","DOI":"10.1007\/978-3-662-47672-7_42"},{"issue":"3","key":"86_CR15","doi-asserted-by":"publisher","first-page":"1064","DOI":"10.1137\/120893549","volume":"43","author":"A Huber","year":"2014","unstructured":"Huber, A., Krokhin, A., Powell, R.: Skew bisubmodularity and valued CSPs. SIAM Journal on Computing 43(3), 1064\u20131084 (2014)","journal-title":"SIAM Journal on Computing"},{"key":"86_CR16","unstructured":"Jeavons, P., Krokhin, A., \u017divn\u00fd, S.: The complexity of valued constraint satisfaction. Bulletin of the EATCS 113, 21\u201355 (2014)"},{"key":"86_CR17","doi-asserted-by":"crossref","unstructured":"Kolmogorov, V., Thapper, J., Z\u017divn\u00fd, S.: The power of linear programming for general-valued CSPs. SIAM Journal on Computing 44(1), 1\u201336 (2015)","DOI":"10.1137\/130945648"},{"key":"86_CR18","doi-asserted-by":"crossref","unstructured":"Kolmogorov, V., Z\u017divn\u00fd, S.: The complexity of conservative valued CSPs. Journal of the ACM 60(2), Article No. 10 (2013)","DOI":"10.1145\/2450142.2450146"},{"key":"86_CR19","doi-asserted-by":"crossref","unstructured":"Kozik, M., Krokhin, A., Valeriote, M., Willard, R.: Characterizations of several Maltsev Conditions. Algebra Universalis (2014) (to appear)","DOI":"10.1007\/s00012-015-0327-2"},{"key":"86_CR20","doi-asserted-by":"crossref","unstructured":"Kun, G., O\u2019Donnell, R., Tamaki, S., Yoshida, Y., Zhou, Y.: Linear programming, width-1 CSPs, and robust satisfaction. In: ITCS 2012, p. 484\u2013495 (2012)","DOI":"10.1145\/2090236.2090274"},{"key":"86_CR21","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/s00012-007-2012-6","volume":"56","author":"B Larose","year":"2007","unstructured":"Larose, B., Z\u00e1dori, L.: Bounded width problems and algebras. Algebra Universalis 56, 439\u2013466 (2007)","journal-title":"Algebra Universalis"},{"key":"86_CR22","doi-asserted-by":"crossref","unstructured":"Kozik, M., Ochremiak, J.: Algebraic Properties of Valued Constraint Satisfaction Problem. In: Proc. ICALP 2015. Springer (2015)","DOI":"10.1007\/978-3-662-47672-7_69"},{"key":"86_CR23","doi-asserted-by":"crossref","unstructured":"Raghavendra, P.: Optimal algorithms and inapproximability results for every CSP? In: Proc. STOC 2008, pp. 245\u2013254. ACM (2008)","DOI":"10.1145\/1374376.1374414"},{"issue":"3","key":"86_CR24","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"HD Sherali","year":"1990","unstructured":"Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal of Discrete Mathematics 3(3), 411\u2013430 (1990)","journal-title":"SIAM Journal of Discrete Mathematics"},{"key":"86_CR25","doi-asserted-by":"crossref","unstructured":"Takhanov, R.: A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem. In: Proc. STACS 2010, pp. 657\u2013668 (2010)","DOI":"10.1007\/978-3-642-14031-0_36"},{"key":"86_CR26","doi-asserted-by":"crossref","unstructured":"Thapper, J., Z\u017divn\u00fd, S.: The power of linear programming for valued CSPs. In: Proc. FOCS 2012, pp. 669\u2013678. IEEE (2012)","DOI":"10.1109\/FOCS.2012.25"},{"key":"86_CR27","doi-asserted-by":"crossref","unstructured":"Thapper, J., Z\u017divn\u00fd, S.: The complexity of finite-valued CSPs. In: Proc. STOC 2013, pp. 695\u2013704. ACM (2013) (February 2015). Full version arXiv:1210.2977v3","DOI":"10.1145\/2488608.2488697"},{"key":"86_CR28","doi-asserted-by":"crossref","unstructured":"Thapper, J., Z\u017divn\u00fd, S.: Necessary Conditions on Tractability of Valued Constraint Languages. Technical report, February 2015. arXiv:1502.03482","DOI":"10.1137\/140990346"},{"key":"86_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1007\/978-3-642-39206-1_68","volume-title":"Automata, Languages, and Programming","author":"H Uppman","year":"2013","unstructured":"Uppman, H.: The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 804\u2013815. Springer, Heidelberg (2013)"},{"key":"86_CR30","doi-asserted-by":"crossref","unstructured":"Yoshida, Y., Zhou, Y.: Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems. In: Proc. ITCS 2014, pp. 423\u2013438. ACM (2014)","DOI":"10.1145\/2554797.2554836"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_86","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T08:44:31Z","timestamp":1676018671000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_86"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_86","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}