乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:41:30Z","timestamp":1740134490668,"version":"3.37.3"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"name":"Center for Industrial Information Technology","award":["4.01"]},{"DOI":"10.13039\/501100004359","name":"Vetenskapsr\u00e4det","doi-asserted-by":"publisher","award":["621-2003-34212006-4532"],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/C543831\/1"],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2008,9]]},"abstract":"\n In the maximum constraint satisfaction problem (MAX CSP), one is given a finite collection of (possibly weighted) constraints on overlapping sets of variables, and the goal is to assign values from a given finite domain to the variables so as to maximize the number (or the total weight, for the weighted case) of satisfied constraints. This problem is NP-hard in general, and, therefore, it is natural to study how restricting the allowed types of constraints affects the approximability of the problem. In this article, we show that any MAX CSP problem with a finite set of allowed constraint types, which includes all fixed-value constraints (i.e., constraints of the form\n x<\/jats:italic>\n =\n a<\/jats:italic>\n ), is either solvable exactly in polynomial time or else is APX-complete, even if the number of occurrences of variables in instances is bounded. Moreover, we present a simple description of all polynomial-time solvable cases of our problem. This description relies on the well-known algebraic combinatorial property of supermodularity.\n <\/jats:p>","DOI":"10.1145\/1391289.1391290","type":"journal-article","created":{"date-parts":[[2008,9,16]],"date-time":"2008-09-16T16:32:40Z","timestamp":1221582760000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["The approximability of MAX CSP with fixed-value constraints"],"prefix":"10.1145","volume":"55","author":[{"given":"Vladimir","family":"Deineko","sequence":"first","affiliation":[{"name":"University of Warwick, Coventry, UK"}]},{"given":"Peter","family":"Jonsson","sequence":"additional","affiliation":[{"name":"Link\u00f6pings Universitet, Link\u00f6pings, Sweden"}]},{"given":"Mikael","family":"Klasson","sequence":"additional","affiliation":[{"name":"Link\u00f6pings Universitet, Link\u00f6pings, Sweden"}]},{"given":"Andrei","family":"Krokhin","sequence":"additional","affiliation":[{"name":"Durham University, Durham, UK"}]}],"member":"320","published-online":{"date-parts":[[2008,9,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00158-3"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Ausiello G. Creszenzi P. Gambosi G. Kann V. Marchetti-Spaccamela A. and Protasi M. 1999. Complexity and Approximation. Springer-Verlag New York. Ausiello G. Creszenzi P. Gambosi G. Kann V. Marchetti-Spaccamela A. and Protasi M. 1999. Complexity and Approximation. Springer-Verlag New York.","DOI":"10.1007\/978-3-642-58412-1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11602613_63"},{"key":"e_1_2_1_4_1","volume-title":"Tech. Rep. TR03-008, Electronic Colloquium on Computational Complexity (ECCC).","author":"Berman P.","year":"2003","unstructured":"Berman , P. , and Karpinski , M . 2003 . Improved approximation lower bounds on small occurrence optimization. Tech. Rep. TR03-008, Electronic Colloquium on Computational Complexity (ECCC). Berman, P., and Karpinski, M. 2003. Improved approximation lower bounds on small occurrence optimization. Tech. Rep. TR03-008, Electronic Colloquium on Computational Complexity (ECCC)."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the Workshop on Computer Science Logic (CSL'03)","volume":"2803","author":"B\u00f6rner F.","unstructured":"B\u00f6rner , F. , Bulatov , A. , Jeavons , P. , and Krokhin , A . 2003. Quantified constraints: Algorithms and complexity . In Proceedings of the Workshop on Computer Science Logic (CSL'03) . Lecture Notes in Computer Science , vol. 2803 . Springer-Verlag, New York, 58--70. B\u00f6rner, F., Bulatov, A., Jeavons, P., and Krokhin, A. 2003. Quantified constraints: Algorithms and complexity. In Proceedings of the Workshop on Computer Science Logic (CSL'03). Lecture Notes in Computer Science, vol. 2803. Springer-Verlag, New York, 58--70."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/788023.789067"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120582.1120584"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.09.005"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)00103-X"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2005.03.003"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1087"},{"key":"e_1_2_1_13_1","volume-title":"SIAM Monographs on Discrete Mathematics and Applications","volume":"7","author":"Creignou N.","unstructured":"Creignou , N. , Khanna , S. , and Sudan , M . 2001. Complexity classifications of Boolean constraint satisfaction problems . SIAM Monographs on Discrete Mathematics and Applications , vol. 7 . Creignou, N., Khanna, S., and Sudan, M. 2001. Complexity classifications of Boolean constraint satisfaction problems. SIAM Monographs on Discrete Mathematics and Applications, vol. 7."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00435-0"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02276883"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100380458"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_2_1_18_1","volume-title":"Submodular Functions and Optimization","author":"Fujishige S.","unstructured":"Fujishige , S. 2005. Submodular Functions and Optimization , 2 nd ed. Annals of Discrete Mathematics, vol. 58 . Elsevier . Fujishige, S. 2005. Submodular Functions and Optimization, 2nd ed. Annals of Discrete Mathematics, vol. 58. Elsevier.","edition":"2"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1167671.1705178"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00032-6"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060700"},{"key":"e_1_2_1_24_1","volume-title":"Surveys in Combinatorics","author":"Hell P.","year":"2003","unstructured":"Hell , P. 2003. Algorithmic aspects of graph homomorphisms . In Surveys in Combinatorics 2003 , C. Wensley, Ed . LMS Lecture Note Series, vol. 307 . Cambridge University Press , Cambridge, MA, 239--276. Hell, P. 2003. Algorithmic aspects of graph homomorphisms. In Surveys in Combinatorics 2003, C. Wensley, Ed. LMS Lecture Note Series, vol. 307. Cambridge University Press, Cambridge, MA, 239--276."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Hell P. and Ne\u0161et\u0159il J. 2004. Graphs and Homomorphisms. Oxford University Press. Hell P. and Ne\u0161et\u0159il J. 2004. Graphs and Homomorphisms. Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502096"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00343-0"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970444644X"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.02.001"},{"key":"e_1_2_1_30_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings 13th Conference on Fundamentals of Computation Theory, FCT'01","author":"Karpinski M.","unstructured":"Karpinski , M. 2001. Approximating bounded degree instances of NP-hard problems . In Proceedings 13th Conference on Fundamentals of Computation Theory, FCT'01 . Lecture Notes in Computer Science , vol. 2138 . Springer-Verlag , New York , 24--34. Karpinski, M. 2001. Approximating bounded degree instances of NP-hard problems. In Proceedings 13th Conference on Fundamentals of Computation Theory, FCT'01. Lecture Notes in Computer Science, vol. 2138. Springer-Verlag, New York, 24--34."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799349948"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447372"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00054-H"},{"key":"e_1_2_1_34_1","volume-title":"Chem.","volume":"207","author":"Krokhin A.","unstructured":"Krokhin , A. , Bulatov , A. , and Jeavons , P . 2005. The complexity of constraint satisfaction: an algebraic approach. In Structural Theory of Automata, Semigroups, and Universal Algebra. NATO Science Series II: Math., Phys ., Chem. , vol. 207 . Springer Verlag, New York, 181--213. Krokhin, A., Bulatov, A., and Jeavons, P. 2005. The complexity of constraint satisfaction: an algebraic approach. In Structural Theory of Automata, Semigroups, and Universal Algebra. NATO Science Series II: Math., Phys., Chem., vol. 207. Springer Verlag, New York, 181--213."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/060669565"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702406510"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)00189-S"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.1989"},{"volume-title":"Princeton University Press","author":"Topkis D.","key":"e_1_2_1_40_1","unstructured":"Topkis , D. 1998. Supermodularity and Complementarity. Princeton University Press , Princeton, NJ . Topkis, D. 1998. Supermodularity and Complementarity. Princeton University Press, Princeton, NJ."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1391289.1391290","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T08:20:26Z","timestamp":1672302026000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1391289.1391290"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,9]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,9]]}},"alternative-id":["10.1145\/1391289.1391290"],"URL":"https:\/\/doi.org\/10.1145\/1391289.1391290","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2008,9]]},"assertion":[{"value":"2005-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-09-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}