Date
2005
Titre de la collection
Lecture Notes in Computer Science
n° dans la collection
3827
Indexation documentaire
Recherche opérationnelle
Subject
Optimization; Decision
Titre du colloque
16th Annual International Symposium on Algorithms and Computation (ISAAC 2005)
Date du colloque
2005
Ville du colloque
Sanya
Pays du colloque
Chine
Titre de l'ouvrage
Algorithms and Computation
16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005, Proceedings
Auteur
Xiaotie, Deng; Dingzhu, Du
Nom de l'éditeur
Springer
Ville de l'éditeur
Berlin
Année
2005
Nombre total de pages
1190
ISBN
978-3-540-30935-2
Auteur
Bazgan, Cristina
Karpinski, Marek
Type
Communication / Conférence
Nombre de pages du document
624-633
Résumé en anglais
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.
