{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T02:04:55Z","timestamp":1725674695143},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642293436"},{"type":"electronic","value":"9783642293443"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-29344-3_16","type":"book-chapter","created":{"date-parts":[[2012,4,10]],"date-time":"2012-04-10T14:19:29Z","timestamp":1334067569000},"page":"184-194","source":"Crossref","is-referenced-by-count":5,"title":["Parameterized Complexity of MaxSat above Average"],"prefix":"10.1007","author":[{"given":"Robert","family":"Crowston","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gregory","family":"Gutin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"Jones","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1007\/s00453-010-9428-7","volume":"61","author":"N. Alon","year":"2011","unstructured":"Alon, N., Gutin, G., Kim, E.J., Szeider, S., Yeo, A.: Solving MAX-r-SAT above a tight lower bound. Algorithmica\u00a061, 638\u2013655 (2011)","journal-title":"Algorithmica"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Alon, N., Spencer, J.: The Probabilistic Method, 2nd edn. Wiley (2000)","DOI":"10.1002\/0471722154"},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guruswami, V., Manokaran, R.: Every permutation CSP of arity 3 is approximation resistant. In: Proc. Computational Complexity 2009, pp. 62\u201373 (2009)","DOI":"10.1109\/CCC.2009.29"},{"key":"16_CR4","doi-asserted-by":"crossref","unstructured":"Crowston, R., Gutin, G., Jones, M., Yeo, A.: A New Lower Bound on the Maximum Number of Satisfied Clauses in Max-SAT and Its Algorithmic Applications. Algorithmica, doi:10.1007\/s00453-011-9550-1","DOI":"10.1007\/s00453-011-9550-1"},{"key":"16_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/978-3-642-13731-0_17","volume-title":"Algorithm Theory - SWAT 2010","author":"R. Crowston","year":"2010","unstructured":"Crowston, R., Gutin, G., Jones, M., Kim, E.J., Ruzsa, I.Z.: Systems of Linear Equations over \n                  \n                    \n                  \n                  $\\mathbb{F}_2$\n                 and Problems Parameterized above Average. In: Kaplan, H. (ed.) SWAT 2010. LNCS, vol.\u00a06139, pp. 164\u2013175. Springer, Heidelberg (2010)"},{"key":"16_CR6","unstructured":"Crowston, R., Fellows, M., Gutin, G., Jones, M., Rosamond, F., Thomass\u00e9, S., Yeo, A.: Simultaneously Satisfying Linear Equations Over \n                  \n                    \n                  \n                  $\\mathbb{F}_2$\n                : MaxLin2 and Max-r-Lin2 Parameterized Above Average. In: Proc. FSTTCS 2011. LIPICS, vol.\u00a013, pp. 229\u2013240 (2011)"},{"key":"16_CR7","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Proc. IPEC 2011","author":"M. Cygan","year":"2012","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: On Multiway Cut Parameterized above Lower Bounds. In: Rossmanith, P. (ed.) IPEC 2011. LNCS, vol.\u00a07112, pp. 1\u201312. Springer, Heidelberg (2012)"},{"key":"16_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"16_CR9","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"issue":"3","key":"16_CR10","doi-asserted-by":"publisher","first-page":"878","DOI":"10.1137\/090756144","volume":"40","author":"V. Guruswami","year":"2011","unstructured":"Guruswami, V., H\u00e5stad, J., Manokaran, R., Raghavendra, P., Charikar, M.: Beating the random ordering is hard: Every ordering CSP is approximation resistant. SIAM J. Comput.\u00a040(3), 878\u2013914 (2011)","journal-title":"SIAM J. Comput."},{"key":"16_CR11","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Manokaran, R., Raghavendra, P.: Beating the random ordering is hard: Inapproximability of maximum acyclic subgraph. In: Proc. FOCS 2008, pp. 573\u2013582 (2008)","DOI":"10.1109\/FOCS.2008.51"},{"key":"16_CR12","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/j.jcss.2011.01.004","volume":"78","author":"G. Gutin","year":"2012","unstructured":"Gutin, G., van Iersel, L., Mnich, M., Yeo, A.: Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables. J. Comput. System Sci.\u00a078, 151\u2013163 (2012)","journal-title":"J. Comput. System Sci."},{"key":"16_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1007\/978-3-642-22953-4_12","volume-title":"Fundamentals of Computation Theory","author":"G. Gutin","year":"2011","unstructured":"Gutin, G., Jones, M., Yeo, A.: A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application. In: Owe, O., Steffen, M., Telle, J.A. (eds.) FCT 2011. LNCS, vol.\u00a06914, pp. 138\u2013147. Springer, Heidelberg (2011)"},{"key":"16_CR14","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1016\/j.jcss.2010.06.001","volume":"77","author":"G. Gutin","year":"2011","unstructured":"Gutin, G., Kim, E.J., Szeider, S., Yeo, A.: A probabilistic approach to problems parameterized above or below tight bounds. J. Comput. Sys. Sci.\u00a077, 422\u2013429 (2011)","journal-title":"J. Comput. Sys. Sci."},{"key":"16_CR15","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Sys. Sci.\u00a062, 367\u2013375 (2001)","journal-title":"J. Comput. Sys. Sci."},{"key":"16_CR16","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Sys. Sci.\u00a063, 512\u2013530 (2001)","journal-title":"J. Comput. Sys. Sci."},{"key":"16_CR17","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Proc. STOC 2002, pp. 767\u2013775 (2002)","DOI":"10.1145\/509907.510017"},{"issue":"2","key":"16_CR18","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1006\/jagm.1998.0996","volume":"31","author":"M. Mahajan","year":"1999","unstructured":"Mahajan, M., Raman, V.: Parameterizing above guaranteed values: MaxSat and MaxCut. J. Algorithms\u00a031(2), 335\u2013354 (1999)","journal-title":"J. Algorithms"},{"key":"#cr-split#-16_CR19.1","doi-asserted-by":"crossref","unstructured":"Mahajan, M., Raman, V., Sikdar, S.: Parameterizing above or below guaranteed values. J. Comput. Sys. Sci.\u00a075(2), 137-153 (2009)","DOI":"10.1016\/j.jcss.2008.08.004"},{"key":"#cr-split#-16_CR19.2","unstructured":"In: Bodlaender, H.L., Langston, M.A. (eds.): IWPEC 2006. LNCS, vol.\u00a04169, pp. 38-49. Springer, Heidelberg (2006)"},{"key":"16_CR20","doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press (2006)","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"16_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1007\/978-3-642-23719-5_33","volume-title":"Algorithms \u2013 ESA 2011","author":"V. Raman","year":"2011","unstructured":"Raman, V., Ramanujan, M.S., Saurabh, S.: Paths, Flowers and Vertex Cover. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol.\u00a06942, pp. 382\u2013393. Springer, Heidelberg (2011)"},{"key":"16_CR22","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0166-218X(84)90081-7","volume":"8","author":"C.A. Tovey","year":"1984","unstructured":"Tovey, C.A.: A simplified satisfiability problem. Discr. Appl. Math.\u00a08, 85\u201389 (1984)","journal-title":"Discr. Appl. Math."}],"container-title":["Lecture Notes in Computer Science","LATIN 2012: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-29344-3_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:35:30Z","timestamp":1620128130000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-29344-3_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642293436","9783642293443"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-29344-3_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}