Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-APX-Reports 2005 Copyright 2005 University of Bonn, Department of Computer Science, Abt. V
8998

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
 Deutsch 		University of Bonn -> Department of Computer Science -> Chair V