Fetching the paper…
Reading the bibliography…
We study the computational complexity of exact minimisation of rational-valued discrete functions.
Finite Markov chains
John G. Kemeny and James Laurie Snell · 1960
Earlier work this paper cites.
Networks of Constraints: Fundamental properties and applications to picture processing
Ugo Montanari · 1974
Earlier work this paper cites.
Syntactic analysis of two-dimensional visual signals in noisy conditions
Michail I. Shlezinger · 1976
Earlier work this paper cites.
Optimal implementation of conjunctive queries in relational data bases
Ashok K. Chandra and Philip M. Merlin · 1977
Earlier work this paper cites.
The Complexity of Satisfiability Problems
Thomas J. Schaefer · 1978
Earlier work this paper cites.
Computers and Intractability: A Guide to the Theory of NP-Completeness
Michael R. Garey and David S. Johnson · 1979
Earlier work this paper cites.
The complexity of facets (and some facets of complexity)
Christos H. Papadimitriou and Mihalis Yannakakis · 1984
Earlier work this paper cites.
Theory of linear and integer programming
Alexander Schrijver · 1986
Earlier work this paper cites.
Geometric Algorithms and Combinatorial Optimization
M. Grötschel, L. Lovasz, and A. Schrijver · 1988
Earlier work this paper cites.
A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems
H. D. Sherali and W. P. Adams · 1990
Earlier work this paper cites.
The core of a graph
Pavol Hell and Jaroslav Nešetřil · 1992
Earlier work this paper cites.
A dichotomy theorem for maximum generalized satisfiability problems
Nadia Creignou · 1995
Earlier work this paper cites.
Graphical Models
Steffen L. Lauritzen · 1996
Earlier work this paper cites.
Closure Properties of Constraints
Peter G. Jeavons, David A. Cohen, and Marc Gyssens · 1997
Earlier work this paper cites.
The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
Tomás Feder and Moshe Y. Vardi · 1998
Earlier work this paper cites.
On the Algebraic Structure of Combinatorial Problems
Peter G. Jeavons · 1998
Earlier work this paper cites.
The partial constraint satisfaction problem: Facets and lifting theorems
Arie Koster, Stan P.M. van Hoesel, and Antoon W.J. Kolen · 1998
Earlier work this paper cites.
Conjunctive-Query Containment and Constraint Satisfaction
Phokion G. Kolaitis and Moshe Y. Vardi · 2000
Earlier work this paper cites.
Complexity Classification of Boolean Constraint Satisfaction Problems
Nadia Creignou, Sanjeev Khanna, and Madhu Sudan · 2001
Earlier work this paper cites.
Some optimal inapproximability results
Johan Håstad · 2001
Earlier work this paper cites.
The approximability of constraint satisfaction problems
Sanjeev Khanna, Madhu Sudan, Luca Trevisan, and David Williamson · 2001
Earlier work this paper cites.
Constraint Processing
Rina Dechter · 2003
Earlier work this paper cites.
A linear programming formulation and approximation algorithms for the metric labeling problem
Chandra Chekuri, Sanjeev Khanna, Joseph Naor, and Leonid Zosin · 2004
Earlier work this paper cites.
Graphs and Homomorphisms
Pavol Hell and Jaroslav Nešetřil · 2004
Earlier work this paper cites.
Classifying the Complexity of Constraints using Finite Algebras
Andrei Bulatov, Andrei Krokhin, and Peter Jeavons · 2005
Earlier work this paper cites.
Supermodular Functions and the Complexity of MAX-CSP
David Cohen, Martin Cooper, Peter Jeavons, and Andrei Krokhin · 2005
Earlier work this paper cites.
Data exchange: getting to the core
Ronald Fagin, Phokion G. Kolaitis, and Lucian Popa · 2005
Earlier work this paper cites.
Solving and analyzing side-chain positioning problems using linear and integer programming
Carleton L. Kingsford, Bernard Chazelle, and Mona Singh · 2005
Cited alongside, same era.
MAP estimation via agreement on trees: message passing and linear programming
M. Wainwright, T. Jaakkola, and A. Willsky · 2005
Cited alongside, same era.
A dichotomy theorem for constraint satisfaction problems on a 3-element set
Andrei Bulatov · 2006
Cited alongside, same era.
An Algebraic Characterisation of Complexity for Valued Constraints
David A. Cohen, Martin C. Cooper, and Peter G. Jeavons · 2006
Cited alongside, same era.
The Complexity of Soft Constraint Satisfaction
David A. Cohen, Martin C. Cooper, Peter G. Jeavons, and Andrei A. Krokhin · 2006
Cited alongside, same era.
The Approximability of Three-valued MAX CSP
Peter Jonsson, Mikael Klasson, and Andrei Krokhin · 2006
Extensions of the Minimum Cost Homomorphism Problem
Rustem Takhanov · 2010
Later among the works it cites.
The dichotomy for conservative constraint satisfaction problems revisited
Libor Barto · 2011
Later among the works it cites.
Complexity of conservative constraint satisfaction problems
Andrei A. Bulatov · 2011
Later among the works it cites.
Hybrid tractability of valued constraint problems
Martin C. Cooper and Stanislav Živný · 2011
Later among the works it cites.
Boolean Functions - Theory, Algorithms, and Applications
Yves Crama and Peter L. Hammer · 2011
Later among the works it cites.
On minimal weighted clones
Páidí Creed and Stanislav Živný · 2011
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
The complexity of homomorphism and constraint satisfaction problems seen from the other side
Martin Grohe · 2007
Cited alongside, same era.
An introduction to hyperplane arrangements
Richard P. Stanley · 2007
Cited alongside, same era.
Buildings – Theory and Applications
Peter Abramenko and Kenneth S. Brown · 2008
Cited alongside, same era.
Minimization of Locally Defined Submodular Functions by Optimal Soft Arc Consistency
Martin C. Cooper · 2008
Cited alongside, same era.
The approximability of Max CSP with fixed-value constraints
Vladimir Deineko, Peter Jonsson, Mikael Klasson, and Andrei Krokhin · 2008
Cited alongside, same era.
Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness
Venkatesan Guruswami and Prasad Raghavendra · 2008
Cited alongside, same era.
Peter Jonsson, Fredrik Kuivinen, and Johan Thapper · 2011
Later among the works it cites.
Robust Satisfiability of Constraint Satisfaction Problems
Libor Barto and Marcin Kozik · 2012
Closest in time.
Tractable triangles and cross-free convexity in discrete optimisation
Martin C. Cooper and Stanislav Živný · 2012
Closest in time.
Constraint optimization problems and bounded tree-width revisited
Tommy Färnqvist · 2012
Closest in time.
Linear programming, width-1 CSPs, and robust satisfaction
Gábor Kun, Ryan O’Donnell, Suguru Tamaki, Yuichi Yoshida, and Yuan Zhou · 2012
Closest in time.
The power of linear programming for valued CSPs
Johan Thapper and Stanislav Živný · 2012
Closest in time.
The complexity of valued constraint satisfaction problems
Stanislav Živný · 2012
Closest in time.
An algebraic theory of complexity for discrete optimisation
David A. Cohen, Martin C. Cooper, Páidí Creed, Peter Jeavons, and Stanislav Živný · 2013
Closest in time.
Robust Satisfiability for CSPs: Hardness and Algorithmic Results
Víctor Dalmau and Andrei A. Krokhin · 2013
Closest in time.
Skew Bisubmodularity and Valued CSPs
Anna Huber, Andrei Krokhin, and Robert Powell · 2013
Closest in time.
The power of linear programming for finite-valued CSPs: a constructive characterization
Vladimir Kolmogorov · 2013
Closest in time.
The complexity of conservative valued CSPs
Vladimir Kolmogorov and Stanislav Živný · 2013
Closest in time.
Tractable hypergraph properties for constraint satisfaction and conjunctive queries
Dániel Marx · 2013
Closest in time.
The complexity of finite-valued CSPs
Johan Thapper and Stanislav Živný · 2013
Closest in time.
The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom
Hannes Uppman · 2013
Closest in time.
Constraint Satisfaction Problems Solvable by Local Consistency Methods
Libor Barto and Marcin Kozik · 2014
Closest in time.
Skew bisubmodularity and valued CSPs
Anna Huber, Andrei Krokhin, and Robert Powell · 2014
Closest in time.
Computational Complexity of the Extended Minimum Cost Homomorphism Problem on Three-Element Domains
Hannes Uppman · 2014
Closest in time.
Discrete Convexity and Polynomial Solvability in Minimum 0-Extension Problems
Hiroshi Hirai · 2015
Closest in time.
The power of linear programming for general-valued CSPs
Vladimir Kolmogorov, Johan Thapper, and Stanislav Živný · 2015
Closest in time.