Date
2005
Collection title
Lecture Notes in Computer Science
Collection Id
3827
Dewey
Recherche opérationnelle
Sujet
Optimization; Decision
Conference name
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
Author
Xiaotie, Deng; Dingzhu, Du
Publisher
Springer
Publisher city
Berlin
Year
2005
Pages number
1190
ISBN
978-3-540-30935-2
Author
Bazgan, Cristina
Karpinski, Marek
Type
Communication / Conférence
Item number of pages
624-633
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.
