A Method to Solve the Weighted Constraint Satisfaction Problem (WCSP)

Marko Berezovsky

FEL CVUT

Abstract

WCSP is a difficult optimization problem, arising e.g. in image analysis. Its special cases include maximum flow problem, maximum cut problem, discrete dynamic programming problem and others. The objective function of the problem is a multivariate function expressed as a sum of functions of one or two variables (i.e., of uni- and bivariate functions). In image analysis applications, the collection of the optimal variable states partitions the image into areas of equaly labeled pixels and thus specifies intuitively coherent regions of various importance/interest in the image.

The talk will review the not-widely-known approach due to M. I. Schlesinger et al. published in 1976. We show the existence of the upper bound of the objective function and how the upper bound can be decreased by equivalent transformations of the original problem. Testing whether a given upper bound is equal to the