liu.seSearch for publications in DiVA
ReferencesLink to record
Permanent link

Direct link
Exploiting Structure in CSP-related Problems
2013 (English)Doktorsavhandling, monografi (Other academic)
Abstract [en]

In this thesis we investigate the computational complexity and approximability of computational problems from the constraint satisfaction framework. An instance of a constraint satisfaction problem (CSP) has three components; a set V of variables, a set D of domain values, and a set of constraints C. The constraints specify a set of variables and associated local conditions on the domain values allowed for each variable, and the objective of a CSP is to assign domain values to the variables, subject to these constraints.

The first main part of the thesis is concerned with studying restrictions on the structure induced by the constraints on the variables for different computational problems related to the CSP. In particular, we examine how to exploit various graph, and hypergraph, acyclicity measures from the literature to find classes of relational structures for which our computational problems become efficiently solvable. Among the problems studied are, such where, in addition to the constraints of a CSP, lists of allowed domain values for each variable are specified (LHom). We also study variants of the CSP where the objective is changed to: counting the number of possible assignments of domain values to the variables given the constraints of a CSP (#CSP), minimising or maximising the cost of an assignment satisfying all constraints given various different ways of assigning costs to assignments (MinHom, Max Sol, and CSP), or maximising the number of satisfied constraints (Max CSP). In several cases, our investigations uncover the largest known (or possible) classes of relational structures for which our problems are efficiently solvable. Moreover, we take a different view on our optimisation problems MinHom and VCSP; instead of considering fixed arbitrary values for some (hyper)graph acyclicity measure associated with the underlying CSP, we consider the problems parameterised by such measures in combination with other basic parameters such as domain size and maximum arity of constraints. In this way, we identify numerous combinations of the considered parameters which make these optimisation problems admit fixed-parameter algorithms.

In the second part of the thesis, we explore the approximability properties of the (weighted) Max CSP problem for graphs. This is a problem which is known to be approximable within some constant ratio, but not believed to be approximable within an arbitrarily small constant ratio. Thus it is of interest to determine the best ratio within which the problem can be approximated, or at least give some bound on this constant. We introduce a novel method for studying approximation ratios which, in the context of Max CSP for graphs, takes the form of a new binary parameter on the space of all graphs. This parameter may, informally, be thought of as a sort of distance between two graphs; knowing the distance between two graphs, we can bound the approximation ratio of one of them, given a bound for the other.

Place, publisher, year, pages
Linköping: Linköping University Electronic Press, 2013. 165 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1496
National Category
Computer Science
Identifiers
urn:nbn:se:liu:diva-85668 (URN)978-91-7519-711-1 (ISBN)oai:DiVA.org:liu-85668 (OAI)
Public defence
2013-02-08, Visionen,Hus B, Campus Valla, Linköpings universitet, Linköping, 13:15 (English)
Opponent
Supervisors
Available from2012-12-17 Created:2012-11-27 Last updated:2012-12-20Bibliographically approved

Open Access in DiVA

fulltext(1347 kB)374 downloads
File information
File name FULLTEXT01.pdfFile size 1347 kBChecksum SHA-512
690f020b6d2e5998d41f05e3e01a0baeb69766ea56dbb3483723d0f3e2330647021b4f260dd893d58fe7a1f5d02bc61926fc92fc790c389843d967bacd60bf28
Typ fulltextMimetype application/pdf
cover(42 kB)66 downloads
File information
File name COVER01.pdfFile size 42 kBChecksum SHA-512
0bc159f85e16b73a56f2d058b2f9658c781c8ccc038514fc17b8223efa75ec380c68c789ec191b5f88c55e73d67f00d124f038d8f86fca30fb79753b8a62d3d7
Typ coverMimetype application/pdf

Search in DiVA

By author/editor
Färnqvist, Tommy
By organisation
Software and SystemsThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Totalt: 374 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
Totalt: 855 hits
ReferencesLink to record
Permanent link

Direct link