Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2005 Copyright 2005 Universität Bonn, Institut für Informatik, 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
 English
Universität Bonn -> Institut für Informatik -> Abteilung V