On the public citation graph
The Power of Linear Programming for Valued CSPs
0 signed · 113 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1006/jctb.2000.1989openalex-snapshot
A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time
inferredcites →https://doi.org/10.1007/11889205_10openalex-snapshot
An Algebraic Characterisation of Complexity for Valued Constraint
inferredcites →https://doi.org/10.1007/978-3-540-48085-3_12openalex-snapshot
Closure Functions and Width 1 Problems
inferredcites →https://doi.org/10.1007/978-3-642-22993-0_23openalex-snapshot
An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection
inferredcites →https://doi.org/10.1007/978-3-642-22993-0_37openalex-snapshot
Submodularity on a Tree: Unifying $L^\natural$ -Convex and Bisubmodular Functions
inferredcites →https://doi.org/10.1007/978-3-642-23786-7_18openalex-snapshot
On Minimal Weighted Clones
inferredcites →https://doi.org/10.1007/978-3-642-23786-7_34openalex-snapshot
Min CSP on Four Elements: Moving beyond Submodularity
inferredcites →https://doi.org/10.1007/978-3-642-32147-4_40openalex-snapshot
Towards Minimizing k-Submodular Functions
inferredcites →https://doi.org/10.1007/s10107-008-0242-9openalex-snapshot
Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
inferredcites →https://doi.org/10.1016/0004-3702(77)90007-8openalex-snapshot
Consistency in networks of relations
inferredcites →https://doi.org/10.1016/0020-0255(74)90008-5openalex-snapshot
Networks of constraints: Fundamental properties and applications to picture processing
inferredcites →https://doi.org/10.1016/j.artint.2003.09.002openalex-snapshot
Arc consistency for soft constraints
inferredcites →https://doi.org/10.1016/j.artint.2006.04.002openalex-snapshot
The complexity of soft constraint satisfaction
inferredcites →https://doi.org/10.1016/j.artint.2010.02.001openalex-snapshot
Soft arc consistency revisited
inferredcites →https://doi.org/10.1016/j.disopt.2011.04.001openalex-snapshot
On the complexity of submodular function minimisation on diamonds
inferredcites →https://doi.org/10.1016/j.tcs.2008.03.015openalex-snapshot
Generalising submodularity and horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
inferredcites →https://doi.org/10.1016/j.tcs.2009.05.022openalex-snapshot
Hard constraint satisfaction problems have hard gaps at location 1
inferredcites →https://doi.org/10.1016/s0304-3975(97)00230-2openalex-snapshot
On the algebraic structure of combinatorial problems
inferredcites →https://doi.org/10.1109/ccc.2010.19openalex-snapshot
On the Unique Games Conjecture (Invited Survey)
inferredcites →https://doi.org/10.1109/focs.2007.40openalex-snapshot
Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling
inferredcites →https://doi.org/10.1109/focs.2009.32openalex-snapshot
Constraint Satisfaction Problems of Bounded Width
inferredcites →https://doi.org/10.1109/lics.2011.25openalex-snapshot
The Dichotomy for Conservative Constraint Satisfaction Problems Revisited
inferredcites →https://doi.org/10.1137/060669565openalex-snapshot
Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction
inferredcites →https://doi.org/10.1137/070708093openalex-snapshot
The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
inferredcites →https://doi.org/10.1137/090775646openalex-snapshot
Tractability and Learnability Arising from Algebras with Few Subpowers
inferredcites →https://doi.org/10.1137/090779346openalex-snapshot
Maximizing Non-monotone Submodular Functions
inferredcites →https://doi.org/10.1137/1.9780898718546openalex-snapshot
Complexity Classifications of Boolean Constraint Satisfaction Problems
inferredcites →https://doi.org/10.1137/130906398openalex-snapshot
An Algebraic Theory of Complexity for Discrete Optimization
inferredcites →https://doi.org/10.1137/s0097539700376676openalex-snapshot
Classifying the Complexity of Constraints Using Finite Algebras
inferredcites →https://doi.org/10.1137/s0097539794266766openalex-snapshot
The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
inferredcites →https://doi.org/10.1137/s0097539799349948openalex-snapshot
The Approximability of Constraint Satisfaction Problems
inferredcites →https://doi.org/10.1137/s0895480103426339openalex-snapshot
Bisubmodular Function Minimization
inferredcites →https://doi.org/10.1145/1120582.1120584openalex-snapshot
A dichotomy theorem for constraint satisfaction problems on a 3-element set
inferredcites →https://doi.org/10.1145/1374376.1374414openalex-snapshot
Optimal algorithms and inapproximability results for every CSP?
inferredcites →https://doi.org/10.1145/1391289.1391290openalex-snapshot
The approximability of MAX CSP with fixed-value constraints
inferredcites →https://doi.org/10.1145/1970398.1970400openalex-snapshot
Complexity of conservative constraint satisfaction problems
inferredcites →https://doi.org/10.1145/2090236.2090274openalex-snapshot
Linear programming, width-1 CSPs, and robust satisfaction
inferredcites →https://doi.org/10.1145/2213977.2214061openalex-snapshot
Robust satisfiability of constraint satisfaction problems
inferredcites →https://doi.org/10.1145/2450142.2450146openalex-snapshot
The complexity of conservative valued CSPs
inferredcites →https://doi.org/10.1145/256303.256306openalex-snapshot
Semiring-based constraint satisfaction and optimization
inferredcites →https://doi.org/10.1145/263867.263489openalex-snapshot
Closure properties of constraints
inferredcites →https://doi.org/10.1145/359642.359654openalex-snapshot
Synthesizing constraint expressions
inferredcites →https://doi.org/10.1145/502090.502096openalex-snapshot
A combinatorial strongly polynomial algorithm for minimizing submodular functions
inferredcites →https://doi.org/10.1145/800133.804350openalex-snapshot
The complexity of satisfiability problems
inferredcites →https://doi.org/10.1561/2200000001openalex-snapshot
Graphical Models, Exponential Families, and Variational Inference
inferredcites →https://doi.org/10.1561/9781601981851openalex-snapshot
Graphical Models, Exponential Families, and Variational Inference
inferredcites →https://doi.org/10.48550/arxiv.1102.2880openalex-snapshot
Min CSP on Four Elements: Moving Beyond Submodularity
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1007/978-3-030-01225-0_16openalex-snapshot
MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models
inferred← citeshttps://doi.org/10.1007/978-3-030-91434-9_3openalex-snapshot
Streaming Algorithms for Budgeted k-Submodular Maximization Problem
inferred← citeshttps://doi.org/10.1007/978-3-319-45587-7_32openalex-snapshot
On a General Framework for Network Representability in Discrete Optimization
inferred← citeshttps://doi.org/10.1007/978-3-319-46475-6_51openalex-snapshot
Complexity of Discrete Energy Minimization Problems
inferred← citeshttps://doi.org/10.1007/978-3-642-32147-4_40openalex-snapshot
Towards Minimizing k-Submodular Functions
inferred← citeshttps://doi.org/10.1007/978-3-642-33974-5_8openalex-snapshot
The Power of Linear Programming
inferred← citeshttps://doi.org/10.1007/978-3-642-39206-1_53openalex-snapshot
The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization
inferred← citeshttps://doi.org/10.1007/978-3-642-39206-1_68openalex-snapshot
The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom
inferred← citeshttps://doi.org/10.1007/978-3-662-47672-7_42openalex-snapshot
A Galois Connection for Valued Constraint Languages of Infinite Size
inferred← citeshttps://doi.org/10.1007/978-3-662-47672-7_86openalex-snapshot
Sherali-Adams Relaxations for Valued CSPs
inferred← citeshttps://doi.org/10.1007/s10107-014-0824-7openalex-snapshot
Discrete convexity and polynomial solvability in minimum 0-extension problems
inferred← citeshttps://doi.org/10.1007/s10472-025-09974-wopenalex-snapshot
Relative-interior solution for the (incomplete) linear assignment problem with applications to the quadratic assignment problem
inferred← citeshttps://doi.org/10.1007/s10601-015-9198-6openalex-snapshot
Tractability in constraint satisfaction problems: a survey
inferred← citeshttps://doi.org/10.1007/s10878-017-0136-yopenalex-snapshot
On a general framework for network representability in discrete optimization
inferred← citeshttps://doi.org/10.1007/s10878-022-00858-xopenalex-snapshot
Maximizing k-submodular functions under budget constraint: applications and streaming algorithms
inferred← citeshttps://doi.org/10.1007/s41233-018-0021-1openalex-snapshot
A usability based approach to designing continuous user biometric authentication system
inferred← citeshttps://doi.org/10.1016/j.cviu.2015.05.002openalex-snapshot
Higher order maximum persistency and comparison theorems
inferred← citeshttps://doi.org/10.1016/j.disopt.2015.07.001openalex-snapshot
L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem
inferred← citeshttps://doi.org/10.1016/j.jcss.2018.03.003openalex-snapshot
Towards a characterization of constant-factor approximable finite-valued CSPs
inferred← citeshttps://doi.org/10.1016/j.jctb.2022.07.005openalex-snapshot
Minimizing submodular functions on diamonds via generalized fractional matroid matchings
inferred← citeshttps://doi.org/10.1109/cvpr.2013.227openalex-snapshot
Universality of the Local Marginal Polytope
inferred← citeshttps://doi.org/10.1109/focs.2016.63openalex-snapshot
Testing Assignments to Constraint Satisfaction Problems
inferred← citeshttps://doi.org/10.1109/focs.2018.00031openalex-snapshot
The Complexity of General-Valued CSPs Seen from the Other Side
inferred← citeshttps://doi.org/10.1109/iccv.2013.288openalex-snapshot
Potts Model, Parametric Maxflow and K-Submodular Functions
inferred← citeshttps://doi.org/10.1109/tevc.2017.2749263openalex-snapshot
Constrained Monotone $k$ -Submodular Function Maximization Using Multiobjective Evolutionary Algorithms With Theoretical Guarantee
inferred← citeshttps://doi.org/10.1109/tpami.2014.2353626openalex-snapshot
Universality of the Local Marginal Polytope
inferred← citeshttps://doi.org/10.1109/tpami.2014.2363465openalex-snapshot
A New Look at Reweighted Message Passing
inferred← citeshttps://doi.org/10.1109/tpami.2014.2363833openalex-snapshot
Marginal Consistency: Upper-Bounding Partition Functions over Commutative Semirings
inferred← citeshttps://doi.org/10.1137/1.9781611973105.127openalex-snapshot
Discrete Convexity and Polynomial Solvability in Minimum 0-Extension Problems: [Extended Abstract]
inferred← citeshttps://doi.org/10.1137/1.9781611973402.108openalex-snapshot
Maximizing Bisubmodular and k-Submodular Functions
inferred← citeshttps://doi.org/10.1137/1.9781611973730.58openalex-snapshot
Towards a Characterization of Constant-Factor Approximable Min CSPs
inferred← citeshttps://doi.org/10.1137/130906398openalex-snapshot
An Algebraic Theory of Complexity for Discrete Optimization
inferred← citeshttps://doi.org/10.1137/130936038openalex-snapshot
Oracle Tractability of Skew Bisubmodular Functions
inferred← citeshttps://doi.org/10.1137/130936415openalex-snapshot
A Min-Max Theorem for Transversal Submodular Functions and Its Implications
inferred← citeshttps://doi.org/10.1137/130945648openalex-snapshot
The Power of Linear Programming for General-Valued CSPs
inferred← citeshttps://doi.org/10.1137/140962838openalex-snapshot
Half-integrality, LP-branching, and FPT Algorithms
inferred← citeshttps://doi.org/10.1137/16m1079245openalex-snapshot
The Power of Sherali--Adams Relaxations for General-Valued CSPs
inferred← citeshttps://doi.org/10.1137/18m121085xopenalex-snapshot
Constant-Query Testability of Assignments to Constraint Satisfaction Problems
inferred← citeshttps://doi.org/10.1137/26m1889795openalex-snapshot
An Exponential Value-Oracle Lower Bound for \({k}\)-Submodular Function Minimization
inferred← citeshttps://doi.org/10.1145/2450142.2450146openalex-snapshot
The complexity of conservative valued CSPs
inferred← citeshttps://doi.org/10.1145/2488608.2488697openalex-snapshot
The complexity of finite-valued CSPs
inferred← citeshttps://doi.org/10.1145/2850419openalex-snapshot
Maximizing k -Submodular Functions and Beyond
inferred← citeshttps://doi.org/10.1145/2898438openalex-snapshot
A Galois Connection for Weighted (Relational) Clones of Infinite Size
inferred← citeshttps://doi.org/10.1145/3458041openalex-snapshot
The Combined Basic LP and Affine IP Relaxation for Promise VCSPs on Infinite Domains
inferred← citeshttps://doi.org/10.1145/3488721openalex-snapshot
Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation
inferred← citeshttps://doi.org/10.1145/3756323openalex-snapshot
The Sherali–Adams and Weisfeiler–Leman Hierarchies in (Promise Valued) Constraint Satisfaction Problems
inferred← citeshttps://doi.org/10.1609/aaai.v29i1.9425openalex-snapshot
Distributed Multiplicative Weights Methods for DCOP
inferred← citeshttps://doi.org/10.1609/aaai.v29i1.9749openalex-snapshot
Binarisation via Dualisation for Valued Constraints
inferred← citeshttps://doi.org/10.1613/jair.1.15604openalex-snapshot
Using Constraint Propagation to Bound Linear Programs
inferred← citeshttps://doi.org/10.3384/diss.diva-116859openalex-snapshot
On Some Combinatorial Optimization Problems : Algorithms and Complexity
inferred← citeshttps://doi.org/10.48550/arxiv.1207.7213openalex-snapshot
The power of linear programming for valued CSPs: a constructive characterization
inferred← citeshttps://doi.org/10.48550/arxiv.1301.0027openalex-snapshot
Three-Element Min-Sol and Conservative Min-Cost-Hom
inferred← citeshttps://doi.org/10.48550/arxiv.1308.1394openalex-snapshot
Computational Complexity of the Minimum Cost Homomorphism Problem on Three-Element Domains
inferred← citeshttps://doi.org/10.48550/arxiv.1309.5469openalex-snapshot
Towards Minimizing k-Submodular Functions
inferred← citeshttps://doi.org/10.48550/arxiv.1406.0373openalex-snapshot
Linear Programming Relaxations for Goldreich's Generators over Non-Binary Alphabets
inferred← citeshttps://doi.org/10.48550/arxiv.2103.00034openalex-snapshot
Beyond Perturbation Stability: LP Recovery Guarantees for MAP Inference on Noisy Stable Instances
inferred← citeshttps://doi.org/10.5555/2627817.2627840openalex-snapshot
Local distribution and the symmetry gap: approximability of multiway partitioning problems
inferred← citeshttps://doi.org/10.7551/mitpress/9969.001.0001openalex-snapshot
Advanced Structured Prediction
inferred← citeshttps://doi.org/10.7551/mitpress/9969.003.0004openalex-snapshot
The Power of LP Relaxation for MAP Inference
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.