Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
7543457 | Discrete Optimization | 2018 | 11 Pages |
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 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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Control and Optimization
Authors
Yuni Iwamasa, Kazuo Murota, Stanislav Živný,