Journal article
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 and Ž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, and Živný...
Expand abstract
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Authors
Funding
Bibliographic Details
- Publisher:
- Association for Computing Machinery Publisher's website
- Journal:
- ACM Transactions on Algorithms Journal website
- Volume:
- 15
- Issue:
- 3
- Article number:
- 44
- Publication date:
- 2019-07-19
- Acceptance date:
- 2019-05-01
- DOI:
- EISSN:
-
1549-6333
- ISSN:
-
1549-6325
Item Description
- Keywords:
- Pubs id:
-
pubs:995305
- UUID:
-
uuid:3fc14d20-b2b8-4df9-891f-30d99591b4a9
- Local pid:
- pubs:995305
- Source identifiers:
-
995305
- Deposit date:
- 2019-05-01
Terms of use
- Copyright holder:
- Association for Computing Machinery
- Copyright date:
- 2019
- Notes:
- © 2019 Association for Computing Machinery.
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record