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

Полное описание

Библиографические подробности
Главные авторы:	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, и др.
Опубликовано: (2018)

Generalising tractable VCSPs defined by symmetric tournament pair multimorphisms
по: Kolmogorov, V, и др.
Опубликовано: (2010)

Discrete convexity in joint winner property
по: Iwamasa, Y, и др.
Опубликовано: (2018)

Beyond boolean surjective VCSPs
по: Matl, G, и др.
Опубликовано: (2019)

Tractable classes of binary CSPs defined by excluded topological minors
по: Cohen, D, и др.
Опубликовано: (2015)

Tractable triangles and cross−free convexity in discrete optimisation
по: Cooper, M, и др.
Опубликовано: (2012)

Using a min-cut generalisation to go beyond Boolean surjective VCSPs
по: Matl, G, и др.
Опубликовано: (2020)

The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
по: Viola, C, и др.
Опубликовано: (2020)

The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
по: Viola, C, и др.
Опубликовано: (2021)

A new hybrid tractable class of soft constraint problems
по: Cooper, M, и др.
Опубликовано: (2010)

Tractable triangles
по: Cooper, M, и др.
Опубликовано: (2011)

Tractable valued constraints
по: Jeavons, P, и др.
Опубликовано: (2012)

Tractable Valued Constraints
по: Jeavons, P, и др.
Опубликовано: (2013)

Tractabilities and Intractabilities on Geometric Intersection Graphs
по: Ryuhei Uehara
Опубликовано: (2013-01-01)

Hybrid tractability of soft constraint problems
по: Cooper, M, и др.
Опубликовано: (2010)

Hybrid tractability of valued constraint problems
по: Cooper, M, и др.
Опубликовано: (2011)

Necessary conditions for tractability of valued CSPs
по: Thapper, J, и др.
Опубликовано: (2015)

Hybrid tractability of soft constraint problems
по: Cooper, M, и др.
Опубликовано: (2010)

Tractable Combinations of Global Constraints
по: Cohen, D, и др.
Опубликовано: (2013)

Tractable combinations of global constraints
по: Cohen, D, и др.
Опубликовано: (2013)

Tractable constraints closed under a binary operation
по: Bulatov, A, и др.
Опубликовано: (2000)

New tractable classes from old
по: Cohen, D, и др.
Опубликовано: (2003)

New Tractable Classes From Old
по: Cohen, D, и др.
Опубликовано: (2003)

A maximal tractable class of soft constraints
по: Cohen, D, и др.
Опубликовано: (2004)

A maximal tractable class of soft constraints
по: Cohen, D, и др.
Опубликовано: (2004)

Counting answers to unions of conjunctive queries: natural tractability criteria and meta-complexity
по: Focke, J, и др.
Опубликовано: (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, и др.
Опубликовано: (2011)

The order encoding: From tractable CSP to tractable SAT
по: Petke, J, и др.
Опубликовано: (2011)

A Tractable and Expressive Class of Marginal Contribution Nets and Its Applications
по: Elkind, E, и др.
Опубликовано: (2009)

Tractable query answering for description logics via query rewriting
по: Perez-Urbina, H, и др.
Опубликовано: (2010)

The order encoding: from tractable CSP to tractable SAT (extended abstract)
по: Petke, J, и др.
Опубликовано: (2011)

Fixed Parameter Tractable Reasoning in DLs via Decomposition.
по: Simancik, F, и др.
Опубликовано: (2011)

Schur m-Power Convexity of a Class of Multiplicatively Convex Functions and Applications
по: Wen Wang, и др.
Опубликовано: (2014-01-01)

Structural rounding: Approximation algorithms for graphs near an algorithmically tractable class
по: Demaine, Erik D, и др.
Опубликовано: (2020)

A Test for Tractability
по: P.G.Jeavons, и др.
Опубликовано: (1996)

Convex hull for intersections of random lines
по: Daniel Berend, и др.
Опубликовано: (2005-01-01)

Hierarchically nested convex VCSP
по: Cooper, M, и др.
Опубликовано: (2011)

Discrete convex analysis: A tool for economics and game theory
по: Kazuo Murota
Опубликовано: (2016-12-01)

Tractable Disjunctive Constraints
по: D.A.Cohen, и др.
Опубликовано: (1997)