The approximability of constraint satisfaction problems

DOI10.1137/S0097539799349948MaRDI QIDQ2706139zbMATH OpenOpenAlexFDO

Authors Sanjeev Khanna, Luca Trevisan, David P. Williamson, Madhu Sudan

Publication date 19 March 2001

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539799349948

zbMATH Keywords

approximation algorithmsapproximation classesapproximation-preserving reductionsBoolean constraint satisfaction problemscomplete problemshardness of approximation

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 1559517
• Near-optimal algorithms for maximum constraint satisfaction problems
• scientific article; zbMATH DE number 1303558
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Hard constraint satisfaction problems have hard gaps at location 1

Cited in

(99)

• Resolution for Max-SAT
• Optimal satisfiability for propositional calculi and constraint satisfaction problems.
• An efficient algorithm for a class of constraint satisfaction problems
• 2 CSPs all are approximable within a constant differential factor
• On the complexity of trial and error for constraint satisfaction problems
• Affine reductions for LPs and SDPs
• The approximability of non-Boolean satisfiability problems and restricted integer programming
• The complexity of Boolean constraint satisfaction local search problems
• Selecting and covering colored points
• On the Hamming distance of constraint satisfaction problems.
• The complexity of minimal satisfiability problems
• On regularity of Max-CSPs and Min-CSPs
• Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
• PCPs and the hardness of generating synthetic data
• The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
• Isomorphic implication
• Minimal distance of propositional models
• Supermodular functions and the complexity of MAX CSP
• A dichotomy for minimum cost graph homomorphisms
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• Approximation of the quadratic set covering problem
• The complexity of soft constraint satisfaction
• The satisfiability constraint gap
• Robustly solvable constraint satisfaction problems
• Universal factor graphs
• On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems
• Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
• Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set
• Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
• Near-optimal algorithms for maximum constraint satisfaction problems
• scientific article; zbMATH DE number 6381632 (Why is no real title available?)
• Parameterized algorithms and kernels for 3-hitting set with parity constraints
• Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
• Complexity of approximating CSP with balance / hard constraints
• Constraint Satisfaction Parameterized by Solution Size
• Limit Behavior of Locally Consistent Constraint Satisfaction Problems
• Optimization, randomized approximability, and Boolean constraint satisfaction problems
• Complexity of approximating CSP with balance/hard constraints
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• Approximability of the Maximum Solution Problem for Certain Families of Algebras
• Simultaneous approximation of constraint satisfaction problems
• Necessary conditions for tractability of valued CSPs
• Give me another one!
• Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems
• Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint
• Strong lower bounds on the approximability of some NPO PB-complete maximization problems
• Tensor decomposition and approximation schemes for constraint satisfaction problems
• MAX ONES Generalized to Larger Domains
• Two edge modification problems without polynomial kernels
• scientific article; zbMATH DE number 1303558 (Why is no real title available?)
• scientific article; zbMATH DE number 1559516 (Why is no real title available?)
• scientific article; zbMATH DE number 1559517 (Why is no real title available?)
• Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers.
• scientific article; zbMATH DE number 2086657 (Why is no real title available?)
• The complexity of valued CSPs
• Approximation Algorithms for CSPs
• Some recent strong inapproximability results
• scientific article; zbMATH DE number 7561584 (Why is no real title available?)
• Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction
• Intractability of assembly sequencing: unit disks in the plane
• The power of linear programming for general-valued CSPs
• The power of Sherali-Adams relaxations for general-valued CSPs
• scientific article; zbMATH DE number 6783493 (Why is no real title available?)
• Bounded Tree-Width and CSP-Related Problems
• On the efficient approximability of constraint satisfaction problems
• Some optimal inapproximability results
• Minimum Cost Homomorphisms to Reflexive Digraphs
• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
• Introduction to the Maximum Solution Problem
• The next whisky bar
• The complexity of conservative valued CSPs
• Approximability of Bounded Occurrence Max Ones
• A survey on the fine-grained complexity of constraint satisfaction problems based on partial polymorphisms
• Optimal polynomial-time compression for Boolean Max CSP
• scientific article; zbMATH DE number 7650083 (Why is no real title available?)
• Parameterized complexity and kernelizability of max ones and exact ones problems
• PTAS for Sparse General-valued CSPs
• The algebraic structure of the densification and the sparsification tasks for CSPs
• On the Boolean connectivity problem for Horn relations
• On approximability of satisfiable k -CSPs: I
• A characterization of efficiently compilable constraint languages
• Parameterized complexity classification for interval constraints
• Flow-augmentation. III: Complexity dichotomy for Boolean CSPS parameterized by the number of unsatisfied constraints
• Faster parameterized algorithms for variants of \textsc{3-hitting set}
• On the tractability landscape of the conditional minisum approval voting rule
• Optimal polynomial-time compression for Boolean Max CSP
• Linearly ordered colourings of hypergraphs
• Courcelle's theorem for Lipschitz continuity
• Maximum and- vs. even-SAT
• Min-CSPs on complete instances. II: Polylogarithmic approximation for Min-NAE-3-SAT
• On the constant-factor approximability of minimum cost constraint satisfaction problems
• Efficient multiple constraint acquisition
• Hard constraint satisfaction problems have hard gaps at location 1
• Differential approximation of MIN SAT, MAX SAT and related problems
• Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights
• Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
• A dichotomy theorem for maximum generalized satisfiability problems.
• Approximability of clausal constraints
• A note on some collapse results of valued constraints

This page was built for publication: The approximability of constraint satisfaction problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2706139)