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

Direct link
Aspects of a Constraint Optimisation Problem
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
2010 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

In this thesis we study a constraint optimisation problem called the maximum solution problem, henceforth referred to as Max Sol. It is defined as the problem of optimising a linear objective function over a constraint satisfaction problem (Csp) instance on a finite domain. Each variable in the instance is given a non-negative rational weight, and each domain element is also assigned a numerical value, for example taken from the natural numbers. From this point of view, the problem is seen to be a natural extension of integer linear programming over a bounded domain. We study both the time complexity of approximating Max Sol, and the time complexity of obtaining an optimal solution. In the latter case, we also construct some exponential-time algorithms.

The algebraic method is a powerful tool for studying Csp-related problems. It was introduced for the decision version of Csp, and has been extended to a number of other problems, including Max Sol. With this technique we establish approximability classifications for certain families of constraint languages, based on algebraic characterisations. We also show how the concept of a core for relational structures can be extended in order to determine when constant unary relations can be added to a constraint language, without changing the computational complexity of finding an optimal solution to Max Sol. Using this result we show that, in a specific sense, when studying the computational complexity of Max Sol, we only need to consider constraint languages with all constant unary relations included.

Some optimisation problems are known to be approximable within some constant ratio, but are not believed to be approximable within an arbitrarily small constant ratio. For such problems, it is of interest to find the best ratio within which the problem can be approximated, or at least give some bounds on this constant. We study this aspect of the (weighted) Max Csp problem for graphs. In this optimisation problem the number of satisfied constraints is supposed to be maximised. We introduce a method for studying approximation ratios which is based on a new parameter on the space of all graphs. Informally, we think of this parameter as an approximation distance; knowing the distance between two graphs, we can bound the approximation ratio of one of them, given a bound for the other. We further show how the basic idea can be implemented also for the Max Sol problem.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press , 2010. , 218 p.
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1294
National Category
Engineering and Technology
URN: urn:nbn:se:liu:diva-52103ISBN: 978-91-7393-464-0OAI: diva2:281774
Public defence
2010-02-05, Visionen, hus B, Campus Valla, Linköpings universitet, Linköping, 13:15 (English)
Available from: 2009-12-21 Created: 2009-12-04 Last updated: 2009-12-21Bibliographically approved

Open Access in DiVA

Aspects of a Constraint Optimisation Problem(1506 kB)299 downloads
File information
File name FULLTEXT01.pdfFile size 1506 kBChecksum SHA-512
Type fulltextMimetype application/pdf
Cover(91 kB)17 downloads
File information
File name COVER01.pdfFile size 91 kBChecksum SHA-512
Type coverMimetype application/pdf

Search in DiVA

By author/editor
Thapper, Johan
By organisation
TCSLAB - Theoretical Computer Science LaboratoryThe Institute of Technology
Engineering and Technology

Search outside of DiVA

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

Total: 2768 hits
ReferencesLink to record
Permanent link

Direct link