Discrete Convexity in Joint Winner Property

Abstract

In this paper, we reveal a relation between joint winner property (JWP) in the field of valued constraint satisfaction problems (VCSPs) and M${}^{♮}$-convexity in the field of discrete convex analysis (DCA). We introduce the M${}^{♮}$-convex completion problem, and show that a function $f$ satisfying the JWP is Z-free if and only if a certain function $\overline{f}$ associated with $f$ is M${}^{♮}$-convex completable. This means that if a function is Z-free, then the function can be minimized in polynomial time via M${}^{♮}$-convex intersection algorithms. Furthermore we propose a new algorithm for Z-free function minimization, which is faster than previous algorithms for some parameter values.

12 pages

References in corpus (2)

• Hybrid tractability of soft constraint problems
• Tractable Triangles and Cross-Free Convexity in Discrete Optimisation

Cited by in corpus (3)

• The quadratic M-convexity testing problem
• Point-width and Max-CSPs
• A tractable class of binary VCSPs via M-convex intersection