Change search
ReferencesLink to record
Permanent link

Direct link
Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
Linköpings universitet, Programvara och system.
Linköpings universitet, Programvara och system.
Linköpings universitet, Programvara och system.
Linköpings universitet, Programvara och system.
Number of Authors: 4
2014 (English)In: Mathematical Foundations of Computer Science 2014: 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II / [ed] Erzsébet Csuhaj-Varjú, Martin Dietzfelbinger, Zoltán Ésik, Springer Berlin/Heidelberg , 2014, 408-419 p.Chapter in book (Refereed)
Abstract [en]

Obtaining lower bounds for NP-hard problems has for a long time been an active area of research. Recent algebraic techniques introduced by Jonsson et al. (SODA 2013) show that the time complexity of the parameterized SAT(·) problem correlates to the lattice of strong partial clones. With this ordering they isolated a relation R such that SAT(R) can be solved at least as fast as any other NP-hard SAT(·) problem. In this paper we extend this method and show that such languages also exist for the max ones problem (Max-Ones(Γ)) and the Boolean valued constraint satisfaction problem over finite-valued constraint languages (VCSP(Δ)). With the help of these languages we relate Max-Ones and VCSP to the exponential time hypothesis in several different ways.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg , 2014. 408-419 p.
Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online) ; 8635
National Category
Computer and Information Science
URN: urn:nbn:se:hj:diva-31615DOI: 10.1007/978-3-662-44465-8_35ISI: 000358254600035ScopusID: 2-s2.0-84906261436ISBN: 978-3-662-44464-1ISBN: 978-3-662-44465-8OAI: diva2:957121
39th International Symposium on Mathematical Foundations of Computer Science (MFCS-2014)
Available from: 2016-09-01 Created: 2016-09-01 Last updated: 2016-09-01Bibliographically approved

Open Access in DiVA

Postprint(284 kB)3 downloads
File information
File name FULLTEXT01.pdfFile size 284 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Schmidt, Johannes
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 3 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 7 hits
ReferencesLink to record
Permanent link

Direct link