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)