A tractable class of binary VCSPs via M-convex intersection

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...

Descripció completa

Dades bibliogràfiques
Autors principals:	Hirai, H, Iwamasa, Y, Murota, K, Zivny, S
Format:	Journal article
Publicat:	Association for Computing Machinery 2019

Ítems similars

Beyond JWP: A tractable class of binary VCSPs via M-convex intersection
per: Hirai, H, et al.
Publicat: (2018)

Generalising tractable VCSPs defined by symmetric tournament pair multimorphisms
per: Kolmogorov, V, et al.
Publicat: (2010)

Discrete convexity in joint winner property
per: Iwamasa, Y, et al.
Publicat: (2018)

Beyond boolean surjective VCSPs
per: Matl, G, et al.
Publicat: (2019)

Tractable classes of binary CSPs defined by excluded topological minors
per: Cohen, D, et al.
Publicat: (2015)

Tractable triangles and cross−free convexity in discrete optimisation
per: Cooper, M, et al.
Publicat: (2012)

Using a min-cut generalisation to go beyond Boolean surjective VCSPs
per: Matl, G, et al.
Publicat: (2020)

The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
per: Viola, C, et al.
Publicat: (2020)

The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
per: Viola, C, et al.
Publicat: (2021)

A new hybrid tractable class of soft constraint problems
per: Cooper, M, et al.
Publicat: (2010)

Tractable triangles
per: Cooper, M, et al.
Publicat: (2011)

Tractable valued constraints
per: Jeavons, P, et al.
Publicat: (2012)

Tractable Valued Constraints
per: Jeavons, P, et al.
Publicat: (2013)

Tractabilities and Intractabilities on Geometric Intersection Graphs
per: Ryuhei Uehara
Publicat: (2013-01-01)

Hybrid tractability of soft constraint problems
per: Cooper, M, et al.
Publicat: (2010)

Hybrid tractability of valued constraint problems
per: Cooper, M, et al.
Publicat: (2011)

Necessary conditions for tractability of valued CSPs
per: Thapper, J, et al.
Publicat: (2015)

Hybrid tractability of soft constraint problems
per: Cooper, M, et al.
Publicat: (2010)

Tractable Combinations of Global Constraints
per: Cohen, D, et al.
Publicat: (2013)

Tractable combinations of global constraints
per: Cohen, D, et al.
Publicat: (2013)

Tractable constraints closed under a binary operation
per: Bulatov, A, et al.
Publicat: (2000)

New tractable classes from old
per: Cohen, D, et al.
Publicat: (2003)

New Tractable Classes From Old
per: Cohen, D, et al.
Publicat: (2003)

A maximal tractable class of soft constraints
per: Cohen, D, et al.
Publicat: (2004)

A maximal tractable class of soft constraints
per: Cohen, D, et al.
Publicat: (2004)

Counting answers to unions of conjunctive queries: natural tractability criteria and meta-complexity
per: Focke, J, et al.
Publicat: (2024)

The tractable "quadratic" class of growth and interest rate processes
per: Gabaix, Xavier
Publicat: (2011)

The order encoding: from tractable CSP to tractable SAT
per: Petke, J, et al.
Publicat: (2011)

The order encoding: From tractable CSP to tractable SAT
per: Petke, J, et al.
Publicat: (2011)

A Tractable and Expressive Class of Marginal Contribution Nets and Its Applications
per: Elkind, E, et al.
Publicat: (2009)

Tractable query answering for description logics via query rewriting
per: Perez-Urbina, H, et al.
Publicat: (2010)

The order encoding: from tractable CSP to tractable SAT (extended abstract)
per: Petke, J, et al.
Publicat: (2011)

Fixed Parameter Tractable Reasoning in DLs via Decomposition.
per: Simancik, F, et al.
Publicat: (2011)

Schur m-Power Convexity of a Class of Multiplicatively Convex Functions and Applications
per: Wen Wang, et al.
Publicat: (2014-01-01)

Structural rounding: Approximation algorithms for graphs near an algorithmically tractable class
per: Demaine, Erik D, et al.
Publicat: (2020)

A Test for Tractability
per: P.G.Jeavons, et al.
Publicat: (1996)

Convex hull for intersections of random lines
per: Daniel Berend, et al.
Publicat: (2005-01-01)

Hierarchically nested convex VCSP
per: Cooper, M, et al.
Publicat: (2011)

Discrete convex analysis: A tool for economics and game theory
per: Kazuo Murota
Publicat: (2016-12-01)

Tractable Disjunctive Constraints
per: D.A.Cohen, et al.
Publicat: (1997)