Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology. (TCSLAB)
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology. (TCSLAB)
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology. (TCSLAB)
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology. (TCSLAB)
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.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online) ; 8635
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:liu:diva-112902DOI: 10.1007/978-3-662-44465-8_35ISI: 000358254600035Scopus ID: 2-s2.0-84906261436ISBN: 978-3-662-44464-1 (print)ISBN: 978-3-662-44465-8 (print)OAI: oai:DiVA.org:liu-112902DiVA: diva2:773656
Conference
39th International Symposium on Mathematical Foundations of Computer Science (MFCS-2014)
Available from: 2014-12-19 Created: 2014-12-19 Last updated: 2017-02-23Bibliographically approved
In thesis
1. On Some Combinatorial Optimization Problems: Algorithms and Complexity
Open this publication in new window or tab >>On Some Combinatorial Optimization Problems: Algorithms and Complexity
2015 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis is about the computational complexity of several classes of combinatorial optimization problems, all related to the constraint satisfaction problems.

A constraint language consists of a domain and a set of relations on the domain. For each such language there is a constraint satisfaction problem (CSP). In this problem we are given a set of variables and a collection of constraints, each of which is constraining some variables with a relation in the language. The goal is to determine if domain values can be assigned to the variables in a way that satisfies all constraints. An important question is for which constraint languages the corresponding CSP can be solved in polynomial time. We study this kind of question for optimization problems related to the CSPs.

The main focus is on extended minimum cost homomorphism problems. These are optimization versions of CSPs where instances come with an objective function given by a weighted sum of unary cost functions, and where the goal is not only to determine if a solution exists, but to find one of minimum cost. We prove a complete classification of the complexity for these problems on three-element domains. We also obtain a classification for the so-called conservative case.

Another class of combinatorial optimization problems are the surjective maximum CSPs. These problems are variants of CSPs where a non-negative weight is attached to each constraint, and the objective is to find a surjective mapping of the variables to values that maximizes the weighted sum of satisfied constraints. The surjectivity requirement causes these problems to behave quite different from for example the minimum cost homomorphism problems, and many powerful techniques are not applicable. We prove a dichotomy for the complexity of the problems in this class on two-element domains. An essential ingredient in the proof is an algorithm that solves a generalized version of the minimum cut problem. This algorithm might be of independent interest.

In a final part we study properties of NP-hard optimization problems. This is done with the aid of restricted forms of polynomial-time reductions that for example preserves solvability in sub-exponential time. Two classes of optimization problems similar to those discussed above are considered, and for both we obtain what may be called an easiest NP-hard problem. We also establish some connections to the exponential time hypothesis.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2015. 32 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1663
Keyword
Computational complexity, optimization, constraint satisfaction problem
National Category
Computer Science
Identifiers
urn:nbn:se:liu:diva-116859 (URN)10.3384/diss.diva-116859 (DOI)978-91-7519-072-3 (ISBN)
Public defence
2015-05-21, Alan Turing, E-huset, Campus Valla, Linköping, 13:15 (English)
Opponent
Supervisors
Funder
CUGS (National Graduate School in Computer Science), 09.01
Available from: 2015-04-23 Created: 2015-04-07 Last updated: 2015-04-27Bibliographically approved

Open Access in DiVA

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

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Jonsson, PeterLagerkvist, VictorSchmidt, JohannesUppman, Hannes
By organisation
Software and SystemsThe Institute of Technology
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 58 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

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 120 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf