A tractable class of binary VCSPs via M-convex intersection
From MaRDI portal
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 v{Z}ivn'{y} 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 v{Z}ivn'{y} 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. In this paper, 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 5852793 (Why is no real title available?)
- scientific article; zbMATH DE number 1865935 (Why is no real title available?)
- scientific article; zbMATH DE number 7561411 (Why is no real title available?)
- scientific article; zbMATH DE number 3422402 (Why is no real title available?)
- A fast algorithm for constructing trees from distance matrices
- A geometric study of the split decomposition
- Beyond JWP: a tractable class of binary VCSPs via M-convex intersection
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Combinatorial optimization. Theory and algorithms
- Convexity and Steinitz's exchange property
- Discrete Convex Analysis
- Discrete convex analysis
- Discrete convexity and polynomial solvability in minimum 0-extension problems
- Discrete convexity in joint winner property
- Geometry of cuts and metrics
- Hybrid tractability of valued constraint problems
- Hybrid tractable classes of constraint problems
- Matrices and matroids for systems analysis
- Nonserial dynamic programming
- Pseudo-Boolean optimization
- Quadratic M-convex and L-convex functions
- Recent developments in discrete convex analysis
- The complexity of general-valued CSPs
- The complexity of reconstructing trees from qualitative characters and subtrees
- The complexity of valued constraint satisfaction problems
- The power of linear programming for general-valued CSPs
- The quadratic M-convexity testing problem
- Tractable triangles and cross-free convexity in discrete optimisation
- Valuated Matroid Intersection I: Optimality Criteria
- Valuated Matroid Intersection II: Algorithms
- Valuated matroids
- Valuated matroids: A new look at the greedy algorithm
- L-convexity on graph structures
- \(M\)-convex functions and tree metrics
Cited in
(4)
This page was built for publication: A tractable class of binary VCSPs via M-convex intersection
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4972691)
