|
|
| |
| Universität Bonn -> Institut für Informatik -> Abteilung V | ||
| CS-Reports 2005 | Copyright 2005 Universität Bonn, Institut für Informatik, Abt. V | |
|
85268 27.06.2005 |
On the Complexity of Global Constraint Satisfaction
Cristina Bazgan and Marek Karpinski [Download PostScript] [Download PDF] We study the computational complexity of decision andoptimization problems that may be expressed as boolean constraintsatisfaction problem with the global cardinality constraints.In this paper we establish a characterization theorem for thedecision problems and derive approximation hardness resultsfor the corresponding global optimization problems. |
|
|
Last Change:
11/05/14 at 10:32:35
|
Universität Bonn -> Institut für Informatik -> Abteilung V | |