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

Direct link
Constraint Optimization Problems and Bounded Tree-width Revisited
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology. (TCSLAB)
2012 (English)Conference paper, Presentation (Other academic)
Abstract [en]

The valued constraint satisfaction problem (VCSP) is an optimization framework originating from artificial intelligence which generalizes the classical constraint satisfaction problem (CSP). In this paper, we are interested in structural properties that can make problems from the VCSP framework, as well as other CSP variants, solvable to optimality in polynomial time. So far, the largest structural class that is known to be polynomial-time solvable to optimality is the class of bounded hypertree width instances introduced by Gottlob et al. Here, larger classes of tractable instances are singled out by using dynamic programming and structural decompositions based on a hypergraph invariant proposed by Grohe and Marx. In the second part of the paper, we take a different view on our optimization problems; instead of considering fixed arbitrary values for some structural invariant of the (hyper)graph structure of the constraints, we consider the problems parameterized by the tree-width of primal, dual, and incidence graphs, combined with several other basic parameters such as domain size and arity. Such parameterizations of plain CSPs have been studied by Samer and Szeider. Here, we extend their framework to encompass our optimization problems, by coupling it with further non-trivial machinery and new reductions. By doing so, we are able to determine numerous combinations of the considered parameters that make our optimization problems admit fixed-parameter algorithms.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2012. 163-179 p.
Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online) ; 7298
National Category
Computer and Information Science
URN: urn:nbn:se:liu:diva-79501DOI: 10.1007/978-3-642-29828-8_11ISBN: 978-3-642-29827-1 (print)ISBN: 978-3-642-29828-8 (online)OAI: diva2:543130
CPAIOR-2012:9th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems, May 28 - June 1, 2012, Nantes, France
Available from: 2012-08-06 Created: 2012-08-06 Last updated: 2014-11-14

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar
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

Altmetric score

Total: 31 hits
ReferencesLink to record
Permanent link

Direct link