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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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
Algorithms and Hardness Results for Some Valued CSPs
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
2009 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

In the Constraint Satisfaction Problem (CSP) one is supposed to find an assignment to a set of variables so that a set of given constraints are satisfied. Many problems, both practical and theoretical, can be modelled as CSPs. As these problems are computationally hard it is interesting to investigate what kind of restrictions of the problems implies computational tractability. In this thesis the computational complexity of restrictions of two optimisation problems which are related to the CSP is studied. In optimisation problems one can also relax the requirements and ask for an approximatively good solution, instead of requiring the optimal one.

The first problem we investigate is Maximum Solution (Max Sol) where one is looking for a solution which satisfies all constraints and also maximises a linear bjective function. The Maximum Solution problem is a generalisation of the well-known integer linear programming problem. In the case when the constraints are equations over an abelian group we obtain tight inapproximability results. We also study Max Sol for so-called maximal constraint languages and a partial classification theorem is obtained in this case. Finally, Max Sol over the boolean domain is studied in a setting where each variable only occurs a bounded number of times.

The second problem is the Maximum Constraint Satisfaction Problem (Max CSP). In this problem one is looking for an assignment which maximises the number of satisfied constraints. We first show that if the constraints are known to give rise to an NP-hard CSP, then one cannot get arbitrarily good approximate solutions in polynomial time, unless P = NP. We use this result to show a similar hardness result for the case when only one constraint relation is used. We also study the submodular function minimisation problem (SFM) on certain finite lattices. There is a strong link between Max CSP and SFM; new tractability results for SFM implies new tractability results for Max CSP. It is conjectured that SFM is the only reason for Max CSP to be tractable, but no one has yet managed to prove this. We obtain new tractability results for SFM on diamonds and evidence which supports the hypothesis that all modular lattices are tractable.

Abstract [sv]

I ett villkorsprogrammeringsproblem är uppgiften att tilldela värden till variabler så att en given mängd villkor blir uppfyllda. Många praktiska problem, så som schemaläggning och planering, kan formuleras som villkorsprogrammeringsproblem och det är därför önskvärt att ha effektiva algoritmer för att hitta lösningar till denna typ av problem.

De generella varianterna av dessa problem är NP-svåra att lösa. Detta innebär att det antagligen inte finns effektiva algoritmer för problemen (om inte P = NP vilket anses vara mycket osannolikt). Av denna anledning förenklar vi problemet genom att studera restriktioner av det och ibland nöjer vi oss med approximativa lösningar.

I den här avhandlingen studeras två varianter av villkorsprogrammeringsproblemet där man inte bara ska hitta en lösning utan hitta en så bra lösning som möjligt. I den första varianten är målet att hitta en tilldelning där samtliga villkor uppfylls och att en viktad summa av variablerna maximeras. Detta problem kan ses som en generalisering av det välkända linjära heltalsprogrammeringsproblemet. I den andra varianten är målet att hitta en tilldelning som uppfyller så många villkor som möjligt.

Då det gäller den första varianten, då man ska hitta en lösning som uppfyller samtliga villkor som också maximerar summan av variablerna, presenteras nya resultat för ett antal specialfall. De så kallade maximala villkorsmängderna studeras och komplexiteten för ett antal av dessa bestäms. Vi studerar också en variant av problemet över den Boolska domänen då antal variabelförekomster är begränsat. I detta fall ger vi en partiell klassifikation över vilka villkorsmängder som är hanterbara och vilka som inte kan lösas effektivt.

För den andra varianten, då man ska uppfylla så många villkor som möjligt, presenteras några nya effektiva algoritmer för vissa restriktioner. I dessa algoritmer löses det mer generella problemet av minimering av submodulära funktioner över vissa ändliga latticar. Vi bevisar också ett resultat som beskriver exakt när det finns effektiva algoritmer då man endast har tillgång till en typ av villkor.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press , 2009. , 227 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1274
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:liu:diva-51687ISBN: 978-91-7393-525-8 (print)OAI: oai:DiVA.org:liu-51687DiVA: diva2:277010
Public defence
2009-12-11, Alan Turing, hus E, Campus Valla, Linköpings universitet, Linköping, 13:15 (English)
Opponent
Supervisors
Available from: 2009-11-13 Created: 2009-11-13 Last updated: 2009-11-23Bibliographically approved

Open Access in DiVA

Algorithms and Hardness Results for Some Valued CSPs(1353 kB)561 downloads
File information
File name FULLTEXT02.pdfFile size 1353 kBChecksum SHA-512
b44289c57b44c8d509d39f05197c6007ab44973e7e5874bc80aded21b759370ab03fa679c8fb840846cda06f64d38d2f88689094f2e2b7f0371c3785f3da646f
Type fulltextMimetype application/pdf
Cover(26 kB)52 downloads
File information
File name COVER01.pdfFile size 26 kBChecksum SHA-512
2982c95a010f9c7a553d44b6390a44bc701b95bbd2be86ac1d44342143436a74e4f457e788d487b05694b4a2e9ad34f006f976adee08e3cf11e29046f71595a6
Type coverMimetype application/pdf

Authority records BETA

Kuivinen, Fredrik

Search in DiVA

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

Search outside of DiVA

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

isbn
urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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