Conference item icon

Conference item

Beyond JWP: A tractable class of binary VCSPs via M-convex intersection

Abstract:

A binary VCSP is a general framework for the minimization problem of a function represented as the sum of unary and binary cost functions. An important line of VCSP research is to investigate what functions can be solved in polynomial time. Cooper–Živný classified the tractability of binary VCSP instances according to the concept of triangle, and showed that the only interesting tractable case is the one induced by the joint winner property (JWP). Recently, Iwamasa–Murota– Živný made a lin...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Publisher's version

Actions


Access Document


Files:
Publisher copy:
10.4230/LIPIcs.STACS.2018.39

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Role:
Author
Japan Society for the Promotion of Science More from this funder
Mitsubishi Foundation More from this funder
Japanese Science and Technology Agency More from this funder
Royal Society More from this funder
Publisher:
Leibniz Center for Informatics. Publisher's website
Publication date:
2018-02-05
Acceptance date:
2017-12-11
DOI:
ISSN:
1868-8969
Pubs id:
pubs:810410
URN:
uri:daba89d6-22d7-4fe3-8356-a902e8a5fab9
UUID:
uuid:daba89d6-22d7-4fe3-8356-a902e8a5fab9
Local pid:
pubs:810410

Terms of use


Metrics


Views and Downloads






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

TO TOP