A tractable class of binary VCSPs via M-convex intersection
<p>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 bi...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Published: |
Association for Computing Machinery
2019
|
| _version_ | 1826268843314511872 |
|---|---|
| author | Hirai, H Iwamasa, Y Murota, K Zivny, S |
| author_facet | Hirai, H Iwamasa, Y Murota, K Zivny, S |
| author_sort | Hirai, H |
| collection | OXFORD |
| description | <p>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ý made a link between VCSP and discrete convex analysis, showing that a function satisfying the JWP can be transformed into a function represented as the sum of two quadratic M-convex functions, which can be minimized in polynomial time via an M-convex intersection algorithm if the value oracle of each M-convex function is given.</p> <p>In this article, we give an algorithmic answer to a natural question: What binary finite-valued CSP instances can be represented as the sum of two quadratic M-convex functions and can be solved in polynomial time via an M-convex intersection algorithm? We solve this problem by devising a polynomial-time algorithm for obtaining a concrete form of the representation in the representable case. Our result presents a larger tractable class of binary finite-valued CSPs, which properly contains the JWP class.</p> |
| first_indexed | 2024-03-06T21:15:48Z |
| format | Journal article |
| id | oxford-uuid:3fc14d20-b2b8-4df9-891f-30d99591b4a9 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T21:15:48Z |
| publishDate | 2019 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:3fc14d20-b2b8-4df9-891f-30d99591b4a92022-03-26T14:33:54ZA tractable class of binary VCSPs via M-convex intersectionJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:3fc14d20-b2b8-4df9-891f-30d99591b4a9Symplectic Elements at OxfordAssociation for Computing Machinery2019Hirai, HIwamasa, YMurota, KZivny, S<p>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ý made a link between VCSP and discrete convex analysis, showing that a function satisfying the JWP can be transformed into a function represented as the sum of two quadratic M-convex functions, which can be minimized in polynomial time via an M-convex intersection algorithm if the value oracle of each M-convex function is given.</p> <p>In this article, we give an algorithmic answer to a natural question: What binary finite-valued CSP instances can be represented as the sum of two quadratic M-convex functions and can be solved in polynomial time via an M-convex intersection algorithm? We solve this problem by devising a polynomial-time algorithm for obtaining a concrete form of the representation in the representable case. Our result presents a larger tractable class of binary finite-valued CSPs, which properly contains the JWP class.</p> |
| spellingShingle | Hirai, H Iwamasa, Y Murota, K Zivny, S A tractable class of binary VCSPs via M-convex intersection |
| title | A tractable class of binary VCSPs via M-convex intersection |
| title_full | A tractable class of binary VCSPs via M-convex intersection |
| title_fullStr | A tractable class of binary VCSPs via M-convex intersection |
| title_full_unstemmed | A tractable class of binary VCSPs via M-convex intersection |
| title_short | A tractable class of binary VCSPs via M-convex intersection |
| title_sort | tractable class of binary vcsps via m convex intersection |
| work_keys_str_mv | AT hiraih atractableclassofbinaryvcspsviamconvexintersection AT iwamasay atractableclassofbinaryvcspsviamconvexintersection AT murotak atractableclassofbinaryvcspsviamconvexintersection AT zivnys atractableclassofbinaryvcspsviamconvexintersection AT hiraih tractableclassofbinaryvcspsviamconvexintersection AT iwamasay tractableclassofbinaryvcspsviamconvexintersection AT murotak tractableclassofbinaryvcspsviamconvexintersection AT zivnys tractableclassofbinaryvcspsviamconvexintersection |