|
|
| |
| University of Bonn -> Department of Computer Science -> Chair V | ||
| CS-Reports 2005 | Copyright 2005 University of Bonn, Department of Computer Science, 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
|
University of Bonn -> Department of Computer Science -> Chair V | |