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
A Microstructure Based Approach to Constraint Satisfaction Optimisation Problems
Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Applied Mathematics.
2005 (English)In: The 18th International FLAIRS Conference,2005, Menlo Park, CA, USA: AAAI Press , 2005, 155- p.Conference paper, Published paper (Refereed)
Abstract [en]

We study two constraint satisfaction optimisation problems: The Max Value problem for CSPs, which, somewhat simplified, aims at maximising the sum of the (weighted) variable values in the solution, and the Max Ind problem, where the goal is to find a satisfiable subinstance of the original instance containing as many variables as possible. Both problems are NP-hard to approximate within n^(1-e), e>0, where n is the number of variables in the problems, which implies that it is of interest to find exact algorithms. By exploiting properties of the microstructure, we construct algorithms for solving instances of these problems with small domain sizes, and then, using a probabilistic reasoning, we show how to get algorithms for more general versions of the problems. The resulting algorithms have running times of O((0.585d)^n) for Max Value (d,2)-CSP, and O((0.503d)^n) for MaxInd (d,2)-CSP. Both algorithms represent the best known theoretical bounds for their respective problem, and, more importantly, the methods used are applicable to a wide range of optimisation problems. 

Place, publisher, year, edition, pages
Menlo Park, CA, USA: AAAI Press , 2005. 155- p.
Keyword [en]
Tvärvetenskap, artificial intelligence, constraint satisfaction, microstructure
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-24610Local ID: 6786OAI: oai:DiVA.org:liu-24610DiVA: diva2:244932
Available from: 2009-10-07 Created: 2009-10-07

Open Access in DiVA

No full text

Authority records BETA

Angelsmark, OlaThapper, Johan

Search in DiVA

By author/editor
Angelsmark, OlaThapper, Johan
By organisation
The Institute of TechnologyTCSLAB - Theoretical Computer Science LaboratoryApplied Mathematics
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 310 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