Journal article icon

Journal article

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 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 inte...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted manuscript

Actions


Access Document


Files:
Publisher copy:
10.1016/j.disopt.2018.01.001

Authors


Iwamasa, Y More by this author
More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
More from this funder
Funding agency for:
Murota, K
More from this funder
Funding agency for:
Murota, K
More from this funder
Funding agency for:
Murota, K
Expand funders...
Publisher:
Elsevier Publisher's website
Journal:
Discrete Optimization Journal website
Volume:
28
Pages:
78-88
Publication date:
2018-01-19
Acceptance date:
2017-01-03
DOI:
ISSN:
1572-5286
Pubs id:
pubs:813639
URN:
uri:ee2daa5e-90f8-4278-87ea-304ac875fb67
UUID:
uuid:ee2daa5e-90f8-4278-87ea-304ac875fb67
Local pid:
pubs:813639

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP