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

Disgrifiad llawn

Manylion Llyfryddiaeth
Prif Awduron:	Hirai, H, Iwamasa, Y, Murota, K, Zivny, S
Fformat:	Journal article
Cyhoeddwyd:	Association for Computing Machinery 2019

Eitemau Tebyg

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

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

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

Beyond boolean surjective VCSPs
gan: Matl, G, et al.
Cyhoeddwyd: (2019)

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

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

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

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

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

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

Tractable triangles
gan: Cooper, M, et al.
Cyhoeddwyd: (2011)

Tractable valued constraints
gan: Jeavons, P, et al.
Cyhoeddwyd: (2012)

Tractable Valued Constraints
gan: Jeavons, P, et al.
Cyhoeddwyd: (2013)

Tractabilities and Intractabilities on Geometric Intersection Graphs
gan: Ryuhei Uehara
Cyhoeddwyd: (2013-01-01)

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

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

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

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

Tractable Combinations of Global Constraints
gan: Cohen, D, et al.
Cyhoeddwyd: (2013)

Tractable combinations of global constraints
gan: Cohen, D, et al.
Cyhoeddwyd: (2013)

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

New tractable classes from old
gan: Cohen, D, et al.
Cyhoeddwyd: (2003)

New Tractable Classes From Old
gan: Cohen, D, et al.
Cyhoeddwyd: (2003)

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

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

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

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

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

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

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

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

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

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

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

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

A Test for Tractability
gan: P.G.Jeavons, et al.
Cyhoeddwyd: (1996)

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

Hierarchically nested convex VCSP
gan: Cooper, M, et al.
Cyhoeddwyd: (2011)

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

Tractable Disjunctive Constraints
gan: D.A.Cohen, et al.
Cyhoeddwyd: (1997)