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

书目详细资料
Main Authors:	Hirai, H, Iwamasa, Y, Murota, K, Zivny, S
格式:	Journal article
出版:	Association for Computing Machinery 2019

相似书籍

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

Generalising tractable VCSPs defined by symmetric tournament pair multimorphisms
由: Kolmogorov, V, et al.
出版: (2010)

Discrete convexity in joint winner property
由: Iwamasa, Y, et al.
出版: (2018)

Beyond boolean surjective VCSPs
由: Matl, G, et al.
出版: (2019)

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

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

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

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

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

A new hybrid tractable class of soft constraint problems
由: Cooper, M, et al.
出版: (2010)

Tractable triangles
由: Cooper, M, et al.
出版: (2011)

Tractable valued constraints
由: Jeavons, P, et al.
出版: (2012)

Tractable Valued Constraints
由: Jeavons, P, et al.
出版: (2013)

Tractabilities and Intractabilities on Geometric Intersection Graphs
由: Ryuhei Uehara
出版: (2013-01-01)

Hybrid tractability of soft constraint problems
由: Cooper, M, et al.
出版: (2010)

Hybrid tractability of valued constraint problems
由: Cooper, M, et al.
出版: (2011)

Necessary conditions for tractability of valued CSPs
由: Thapper, J, et al.
出版: (2015)

Hybrid tractability of soft constraint problems
由: Cooper, M, et al.
出版: (2010)

Tractable Combinations of Global Constraints
由: Cohen, D, et al.
出版: (2013)

Tractable combinations of global constraints
由: Cohen, D, et al.
出版: (2013)

Tractable constraints closed under a binary operation
由: Bulatov, A, et al.
出版: (2000)

New tractable classes from old
由: Cohen, D, et al.
出版: (2003)

New Tractable Classes From Old
由: Cohen, D, et al.
出版: (2003)

A maximal tractable class of soft constraints
由: Cohen, D, et al.
出版: (2004)

A maximal tractable class of soft constraints
由: Cohen, D, et al.
出版: (2004)

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

The tractable "quadratic" class of growth and interest rate processes
由: Gabaix, Xavier
出版: (2011)

The order encoding: from tractable CSP to tractable SAT
由: Petke, J, et al.
出版: (2011)

The order encoding: From tractable CSP to tractable SAT
由: Petke, J, et al.
出版: (2011)

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

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

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

Fixed Parameter Tractable Reasoning in DLs via Decomposition.
由: Simancik, F, et al.
出版: (2011)

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

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

A Test for Tractability
由: P.G.Jeavons, et al.
出版: (1996)

Convex hull for intersections of random lines
由: Daniel Berend, et al.
出版: (2005-01-01)

Hierarchically nested convex VCSP
由: Cooper, M, et al.
出版: (2011)

Discrete convex analysis: A tool for economics and game theory
由: Kazuo Murota
出版: (2016-12-01)

Tractable Disjunctive Constraints
由: D.A.Cohen, et al.
出版: (1997)