{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,6]],"date-time":"2025-01-06T04:10:03Z","timestamp":1736136603160,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540309352"},{"type":"electronic","value":"9783540324263"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11602613_63","type":"book-chapter","created":{"date-parts":[[2005,12,2]],"date-time":"2005-12-02T08:24:24Z","timestamp":1133511864000},"page":"624-633","source":"Crossref","is-referenced-by-count":5,"title":["On the Complexity of Global Constraint Satisfaction"],"prefix":"10.1007","author":[{"given":"Cristina","family":"Bazgan","sequence":"first","affiliation":[]},{"given":"Marek","family":"Karpinski","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"63_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Rao, S., Vazirani, U.: Expander flows and a $\\sqrt{\\log n}$ -approximation to sparsest cut. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), pp. 222\u2013231 (2004)","DOI":"10.1145\/1007352.1007355"},{"key":"63_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/3-540-36136-7_17","volume-title":"Algorithms and Computation","author":"M. Blaser","year":"2002","unstructured":"Blaser, M., Manthey, B.: Improved Approximation Algorithms for Max 2Sat with Cardinality Constraint. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol.\u00a02518, pp. 187\u2013198. Springer, Heidelberg (2002)"},{"issue":"3","key":"63_CR3","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1006\/jcss.1995.1087","volume":"51","author":"N. Creignou","year":"1995","unstructured":"Creignou, N.: A dichotomy theorem for maximum generalized satisfiability problems. Journal of Computer and System Sciences\u00a051(3), 511\u2013522 (1995)","journal-title":"Journal of Computer and System Sciences"},{"key":"63_CR4","doi-asserted-by":"crossref","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity Classifications of Boolean Constraint Satisfaction Problems. Monographs on Discrete Mathematics and Applications (2001)","DOI":"10.1137\/1.9780898718546"},{"key":"63_CR5","doi-asserted-by":"crossref","unstructured":"Feige, U.: Relations between average case complexity and approximation complexity. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC ), pp. 534\u2013543 (2002)","DOI":"10.1145\/509907.509985"},{"key":"63_CR6","doi-asserted-by":"crossref","unstructured":"Feige, U., Krauthgamer, R.: A polylogarithmic approximation of the Minimum Bisection. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pp. 105\u2013115 (2000)","DOI":"10.1109\/SFCS.2000.892070"},{"key":"63_CR7","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1006\/jagm.2001.1183","volume":"41","author":"U. Feige","year":"2001","unstructured":"Feige, U., Langberg, M.: Approximation Algorithms for Maximization Problems arising in Graph Partitioning. Journal of Algorithms\u00a041, 174\u2013211 (2001)","journal-title":"Journal of Algorithms"},{"key":"63_CR8","volume-title":"Computers and intractability. A guide to the theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman, San Francisco (1979)"},{"key":"63_CR9","doi-asserted-by":"crossref","unstructured":"Garg, N., Vazirani, V., Yannakakis, M.: Approximate max-flow min-(multi)cut theorems and their applications. In: Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC ), pp. 698\u2013707 (1993)","DOI":"10.1145\/167088.167266"},{"key":"63_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1007\/3-540-45535-3_17","volume-title":"Integer Programming and Combinatorial Optimization","author":"E. Halperin","year":"2001","unstructured":"Halperin, E., Zwick, U.: A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems. In: Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol.\u00a02081, pp. 210\u2013225. Springer, Heidelberg (2001)"},{"key":"63_CR11","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC 1997), pp. 1\u201310 (1997)","DOI":"10.1145\/258533.258536"},{"key":"63_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/978-3-540-39658-1_29","volume-title":"Algorithms - ESA 2003","author":"T. Hofmeister","year":"2003","unstructured":"Hofmeister, T.: An Approximation Algorithm for Max 2Sat with Cardinality Constraint. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol.\u00a02832, pp. 301\u2013312. Springer, Heidelberg (2003)"},{"key":"63_CR13","unstructured":"Holmerin, J.: PCP with Global Constraints \u2013 Balanced Homogeneous Linear Equations (manuscript 2002)"},{"key":"63_CR14","doi-asserted-by":"crossref","unstructured":"Holmerin, J., Khot, S.: A strong inapproximability result for a generalization of Minimum Bisection. In: Proceedings of the 18th IEEE Conference on Computational Complexity, pp. 371\u2013378 (2003)","DOI":"10.1109\/CCC.2003.1214436"},{"key":"63_CR15","doi-asserted-by":"crossref","unstructured":"Holmerin, J., Khot, S.: A new PCP Outer Verifier with Applications to Homogeneous Linear Equations and Max-Bisection. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC 2004), pp. 11\u201317 (2004)","DOI":"10.1145\/1007352.1007362"},{"key":"63_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/978-3-540-30538-5_29","volume-title":"FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science","author":"G. J\u00e4ger","year":"2004","unstructured":"J\u00e4ger, G., Srivastav, A.: Improved Approximation Algorithms for Maximum Graph Partitioning Problems. In: Lodaya, K., Mahajan, M. (eds.) FSTTCS 2004. LNCS, vol.\u00a03328, pp. 348\u2013359. Springer, Heidelberg (2004)"},{"key":"#cr-split#-63_CR17.1","doi-asserted-by":"crossref","unstructured":"Khanna, S., Motwani, R., Sudan, M., Vazirani, U.: On syntactic versus computational views of approximability. In: Proceedings of the 35th Annual IEEE Annual Symposium on Foundations of Computer Science, pp. 819???830 (1994);","DOI":"10.1109\/SFCS.1994.365712"},{"key":"#cr-split#-63_CR17.2","doi-asserted-by":"crossref","unstructured":"Also published in SIAM Journal on Computing??28(1), 164???191 (1999)","DOI":"10.1137\/S0097539795286612"},{"key":"63_CR18","unstructured":"Khanna, S., Sudan, M.: The optimization complexity of constraint satisfaction problems. Technical note STAN-CS-TN-96-29, Stanford University, CA (1996)"},{"key":"63_CR19","doi-asserted-by":"crossref","unstructured":"Khanna, S., Sudan, M., Trevisan, L.: Constraint Satisfaction: the Approximability of Minimization Problems. In: Proceedings of 12th IEEE Computational Complexity, pp. 282\u2013296 (1997)","DOI":"10.1109\/CCC.1997.612323"},{"issue":"6","key":"63_CR20","doi-asserted-by":"publisher","first-page":"1863","DOI":"10.1137\/S0097539799349948","volume":"30","author":"S. Khanna","year":"2001","unstructured":"Khanna, S., Sudan, M., Trevisan, L., Williamson, D.P.: The Approximability of Constraint Satisfaction Problems. SIAM Journal of Computing\u00a030(6), 1863\u20131920 (2001)","journal-title":"SIAM Journal of Computing"},{"key":"63_CR21","doi-asserted-by":"crossref","unstructured":"Khanna, S., Sudan, M., Williamson, D.: A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction. In: Proceedings of 29th ACM Symposium on Theory of Computing (STOC 1997), pp. 11\u201320 (1997)","DOI":"10.1145\/258533.258538"},{"key":"63_CR22","doi-asserted-by":"crossref","unstructured":"Khot, S.: Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique. In: Proceedings of the 45th Annual IEEE Annual Symposium on Foundations of Computer Science (FOCS 2004), pp. 136\u2013145 (2004)","DOI":"10.1109\/FOCS.2004.59"},{"key":"63_CR23","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. Journal of Computing and System Science\u00a043, 425\u2013440 (1991)","journal-title":"Journal of Computing and System Science"},{"key":"63_CR24","doi-asserted-by":"crossref","unstructured":"Schaefer, T.: The complexity of satisfiability problems. In: Conference Record of the 10th Annual ACM Symposium on Theory and Computing (STOC ), pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"issue":"3","key":"63_CR25","doi-asserted-by":"crossref","first-page":"398","DOI":"10.1007\/s00453-001-0019-5","volume":"30","author":"M.I. Sviridenko","year":"2001","unstructured":"Sviridenko, M.I.: Best possible approximation algorithm for MAX SAT with cardinality constraint. Algorithmica\u00a030(3), 398\u2013405 (2001)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11602613_63.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,6]],"date-time":"2025-01-06T03:05:37Z","timestamp":1736132737000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11602613_63"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540309352","9783540324263"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/11602613_63","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}