{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T12:05:50Z","timestamp":1742990750247,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662444641"},{"type":"electronic","value":"9783662444658"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-44465-8_35","type":"book-chapter","created":{"date-parts":[[2014,8,12]],"date-time":"2014-08-12T10:33:02Z","timestamp":1407839582000},"page":"408-419","source":"Crossref","is-referenced-by-count":3,"title":["Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis"],"prefix":"10.1007","author":[{"given":"Peter","family":"Jonsson","sequence":"first","affiliation":[]},{"given":"Victor","family":"Lagerkvist","sequence":"additional","affiliation":[]},{"given":"Johannes","family":"Schmidt","sequence":"additional","affiliation":[]},{"given":"Hannes","family":"Uppman","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"6","key":"35_CR1","doi-asserted-by":"publisher","first-page":"1704","DOI":"10.1137\/090772873","volume":"41","author":"J. Batson","year":"2012","unstructured":"Batson, J., Spielman, D.A., Srivastava, N.: Twice-ramanujan sparsifiers. SIAM Journal on Computing\u00a041(6), 1704\u20131721 (2012)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"35_CR2","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1145\/954092.954101","volume":"34","author":"E. B\u00f6hler","year":"2003","unstructured":"B\u00f6hler, E., Creignou, N., Reith, S., Vollmer, H.: Playing with Boolean blocks, part I: Post\u2019s lattice with applications to complexity theory. ACM SIGACT-Newsletter\u00a034(4), 38\u201352 (2003)","journal-title":"ACM SIGACT-Newsletter"},{"issue":"11","key":"35_CR3","doi-asserted-by":"publisher","first-page":"983","DOI":"10.1016\/j.artint.2006.04.002","volume":"170","author":"D.A. Cohen","year":"2006","unstructured":"Cohen, D.A., Cooper, M.C., Jeavons, P.G., Krokhin, A.A.: The complexity of soft constraint satisfaction. Artificial Intelligence\u00a0170(11), 983\u20131016 (2006)","journal-title":"Artificial Intelligence"},{"issue":"6","key":"35_CR4","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1051\/ita\/1997310604991","volume":"31","author":"N. Creignou","year":"1997","unstructured":"Creignou, N., H\u00e9brard, J.J.: On generating all solutions of generalized satisfiability problems. Informatique Th\u00e9orique et Applications\u00a031(6), 499\u2013511 (1997)","journal-title":"Informatique Th\u00e9orique et Applications"},{"issue":"2","key":"35_CR5","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. Journal of Computer and System Sciences\u00a062(2), 367\u2013375 (2001)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"35_CR6","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? Journal of Computer and System Sciences\u00a063(4), 512\u2013530 (2001)","journal-title":"Journal of Computer and System Sciences"},{"key":"35_CR7","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0304-3975(97)00230-2","volume":"200","author":"P. Jeavons","year":"1998","unstructured":"Jeavons, P.: On the algebraic structure of combinatorial problems. Theoretical Computer Science\u00a0200, 185\u2013204 (1998)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"35_CR8","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P. Jeavons","year":"1997","unstructured":"Jeavons, P., Cohen, D., Gyssens, M.: Closure properties of constraints. Journal of the ACM\u00a044(4), 527\u2013548 (1997)","journal-title":"Journal of the ACM"},{"key":"35_CR9","doi-asserted-by":"crossref","unstructured":"Jonsson, P., Lagerkvist, V., Nordh, G., Zanuttini, B.: Complexity of SAT problems, clone theory and the exponential time hypothesis. In: Khanna, S. (ed.) SODA 2013, pp. 1264\u20131277. SIAM (2013)","DOI":"10.1137\/1.9781611973105.92"},{"key":"35_CR10","doi-asserted-by":"crossref","unstructured":"Jonsson, P., Lagerkvist, V., Schmidt, J., Uppman, H.: Relating the time complexity of optimization problems in light of the exponential-time hypothesis. CoRR, abs\/1406.3247 (2014)","DOI":"10.1007\/978-3-662-44465-8_35"},{"issue":"6","key":"35_CR11","doi-asserted-by":"publisher","first-page":"1863","DOI":"10.1137\/S0097539799349948","volume":"30","author":"S. Khanna","year":"2000","unstructured":"Khanna, S., Sudan, M., Trevisan, L., Williamson, D.: The approximability of constraint satisfaction problems. SIAM Journal on Computing\u00a030(6), 1863\u20131920 (2000)","journal-title":"SIAM Journal on Computing"},{"issue":"9","key":"35_CR12","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1016\/j.ipl.2014.03.011","volume":"114","author":"V. Lagerkvist","year":"2014","unstructured":"Lagerkvist, V.: Weak bases of Boolean co-clones. Information Processing Letters\u00a0114(9), 462\u2013468 (2014)","journal-title":"Information Processing Letters"},{"key":"35_CR13","series-title":"Springer Monographs in Mathematics","volume-title":"Function Algebras on Finite Sets: Basic Course on Many-Valued Logic and Clone Theory","author":"D. Lau","year":"2006","unstructured":"Lau, D.: Function Algebras on Finite Sets: Basic Course on Many-Valued Logic and Clone Theory. Springer Monographs in Mathematics. Springer-Verlag New York, Inc., Secaucus (2006)"},{"key":"35_CR14","first-page":"41","volume":"105","author":"D. Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bulletin of the EATCS\u00a0105, 41\u201372 (2011)","journal-title":"Bulletin of the EATCS"},{"key":"35_CR15","first-page":"1","volume":"5","author":"E. Post","year":"1941","unstructured":"Post, E.: The two-valued iterative systems of mathematical logic. Annals of Mathematical Studies\u00a05, 1\u2013122 (1941)","journal-title":"Annals of Mathematical Studies"},{"key":"35_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"774","DOI":"10.1007\/978-3-642-31594-7_65","volume-title":"Automata, Languages, and Programming","author":"R. Santhanam","year":"2012","unstructured":"Santhanam, R., Srinivasan, S.: On the limits of sparsification. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 774\u2013785. Springer, Heidelberg (2012)"},{"key":"35_CR17","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings 10th Symposium on Theory of Computing, pp. 216\u2013226. ACM Press (1978)","DOI":"10.1145\/800133.804350"},{"key":"35_CR18","unstructured":"Schnoor, I.: The weak base method for constraint satisfaction. PhD thesis, Gottfried Wilhelm Leibniz Universit\u00e4t, Hannover, Germany (2008)"},{"key":"35_CR19","unstructured":"Thapper, J.: Aspects of a Constraint Optimisation Problem. PhD thesis, Link\u00f6ping University, The Institute of Technology (2010)"},{"key":"35_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/3-540-36478-1_17","volume-title":"Combinatorial Optimization - Eureka, You Shrink!","author":"G. Woeginger","year":"2003","unstructured":"Woeginger, G.: Exact algorithms for NP-hard problems: A survey. In: J\u00fcnger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization - Eureka, You Shrink! LNCS, vol.\u00a02570, pp. 185\u2013207. Springer, Heidelberg (2003)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2014"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44465-8_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,12]],"date-time":"2024-07-12T09:04:20Z","timestamp":1720775060000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-44465-8_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662444641","9783662444658"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44465-8_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}