Thumbnail

On the Complexity of Global Constraint Satisfaction

Bazgan, Cristina; Karpinski, Marek (2005), On the Complexity of Global Constraint Satisfaction, in Xiaotie, Deng; Dingzhu, Du, Algorithms and Computation 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005, Proceedings, Springer : Berlin, p. 624-633

View/Open
Type
Communication / Conférence
Date
2005
Conference title
16th Annual International Symposium on Algorithms and Computation (ISAAC 2005)
Conference date
2005
Conference city
Sanya
Conference country
Chine
Book title
Algorithms and Computation 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005, Proceedings
Book author
Xiaotie, Deng; Dingzhu, Du
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
3827
Published in
Berlin
ISBN
978-3-540-30935-2
Number of pages
1190
Pages
624-633
Publication identifier
Metadata
Show full item record
Author(s)
Bazgan, Cristina
Karpinski, Marek
Abstract (EN)
We study the computational complexity of decision and optimization problems that may be expressed as boolean contraint satisfaction problem with the global cardinality constraints. In this paper we establish a characterization theorem for the decision problems and derive some new approximation hardness results for the corresponding global optimization problems.
Subjects / Keywords
Optimization; Decision