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

Actions


Access Document


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

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
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
Journal:
35th International Symposium on Theoretical Aspects of Computer Science Journal website
Host title:
35th International Symposium on Theoretical Aspects of Computer Science
Publication date:
2018-02-01
Acceptance date:
2017-12-11
DOI:
ISSN:
1868-8969
Source identifiers:
810410
Keywords:
Pubs id:
pubs:810410
UUID:
uuid:daba89d6-22d7-4fe3-8356-a902e8a5fab9
Local pid:
pubs:810410
Deposit date:
2017-12-12

Terms of use


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