• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

On the Complexity of Global Constraint Satisfaction

Thumbnail
View/Open
complexity_bazgan.PDF (328.2Kb)
Date
2005
Collection title
Lecture Notes in Computer Science
Collection Id
3827
Dewey
Recherche opérationnelle
Sujet
Optimization; Decision
DOI
http://dx.doi.org/10.1007/11602613_63
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
Book URL
http://dx.doi.org/10.1007/11602613
URI
https://basepub.dauphine.fr/handle/123456789/5869
Collections
  • LAMSADE : Publications
Metadata
Show full item record
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.