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

Fuld beskrivelse

Bibliografiske detaljer
Main Authors:	Hirai, H, Iwamasa, Y, Murota, K, Zivny, S
Format:	Journal article
Udgivet:	Association for Computing Machinery 2019

Lignende værker

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

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

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

Beyond boolean surjective VCSPs
af: Matl, G, et al.
Udgivet: (2019)

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

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

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

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

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

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

Tractable triangles
af: Cooper, M, et al.
Udgivet: (2011)

Tractable valued constraints
af: Jeavons, P, et al.
Udgivet: (2012)

Tractable Valued Constraints
af: Jeavons, P, et al.
Udgivet: (2013)

Tractabilities and Intractabilities on Geometric Intersection Graphs
af: Ryuhei Uehara
Udgivet: (2013-01-01)

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

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

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

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

Tractable Combinations of Global Constraints
af: Cohen, D, et al.
Udgivet: (2013)

Tractable combinations of global constraints
af: Cohen, D, et al.
Udgivet: (2013)

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

New tractable classes from old
af: Cohen, D, et al.
Udgivet: (2003)

New Tractable Classes From Old
af: Cohen, D, et al.
Udgivet: (2003)

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

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

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

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

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

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

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

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

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

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

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

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

A Test for Tractability
af: P.G.Jeavons, et al.
Udgivet: (1996)

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

Hierarchically nested convex VCSP
af: Cooper, M, et al.
Udgivet: (2011)

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

Tractable Disjunctive Constraints
af: D.A.Cohen, et al.
Udgivet: (1997)