Random constraint satisfaction: easy generation of hard (satisfiable) instances
From MaRDI portal
Publication:1028939
DOI10.1016/j.artint.2007.04.001zbMath1168.68554MaRDI QIDQ1028939
Ke Xu, Christophe Lecoutre, Frédéric Boussemart, Fred Hemery
Publication date: 9 July 2009
Published in: Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.artint.2007.04.001
68Q25: Analysis of algorithms and problem complexity
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Related Items
Bounding the scaling window of random constraint satisfaction problems, A general model and thresholds for random constraint satisfaction problems, STR2: optimized simple tabular reduction for table constraints, On the phase transitions of random \(k\)-constraint satisfaction problems, Local search with edge weighting and configuration checking heuristics for minimum vertex cover, Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability, The scaling window of the model \(d\)-\(k\)-CSP, An upper (lower) bound for Max (Min) CSP, On the parameterized vertex cover problem for graphs with perfect matching, Reasoning from last conflict(s) in constraint programming, Threshold behaviors of a random constraint satisfaction problem with exact phase transitions, Incomplete inference for graph problems, Weight-based heuristics for constraint satisfaction and combinatorial optimization problems, STR3: a path-optimal filtering algorithm for table constraints, Optimal and efficient filtering algorithms for table constraints, Large hypertree width for sparse random hypergraphs, On the constraint length of random \(k\)-CSP, A taxonomy of exact methods for partial Max-SAT, Complete Boolean satisfiability solving algorithms based on local search, PHASE TRANSITIONS OF EXPSPACE-COMPLETE PROBLEMS: A FURTHER STEP, NEW WORST-CASE UPPER BOUND FOR COUNTING EXACT SATISFIABILITY, Two Hardness Results on Feedback Vertex Sets, Super Solutions of Random Instances of Satisfiability, A Model to Study Phase Transition and Plateaus in Relational Learning
Cites Work
- Consistency in networks of relations
- Boosting complete techniques thanks to local search methods
- Exploiting the deep structure of constraint problems
- Many hard examples in exact phase transitions
- An optimal coarse-grained arc consistency algorithm
- An empirical study of phase transitions in binary constraint satisfaction problems
- Locating the phase transition in binary constraint satisfaction problems
- Generalized Arc Consistency for Positive Table Constraints
- Short proofs are narrow—resolution made simple
- Models for Random Constraint Satisfaction Problems
- Theory and Applications of Satisfiability Testing
- Principles and Practice of Constraint Programming – CP 2004
- Principles and Practice of Constraint Programming – CP 2004
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
- Random constraint satisfaction: A more accurate picture
- Random constraint satisfaction: Flaws and structure
- Constructing an asymptotic phase transition in random binary constraint satisfaction problems
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
