On the Complexity of Global Constraint Satisfaction | Zendy

Cristina Bazgan | Zendy; Marek Karpiński | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On the Complexity of Global Constraint Satisfaction

Author(s) -

Cristina Bazgan,

Marek Karpiński

Publication year - 2005

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-30935-7

DOI - 10.1007/11602613_63

Subject(s) - cardinality (data modeling) , constraint satisfaction problem , computer science , constraint satisfaction , computational complexity theory , constraint satisfaction dual problem , mathematical optimization , local consistency , constraint (computer aided design) , complexity of constraint satisfaction , theoretical computer science , algorithm , mathematics , artificial intelligence , data mining , probabilistic logic , geometry

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research