scientific article
From MaRDI portal
zbMath0747.68064MaRDI QIDQ4012216
Peter C. Cheeseman, Bob Kanefsky, William M. Taylor
Publication date: 27 September 1992
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items
Generic properties of a computational task predict human effort and performance, The computational complexity of propositional STRIPS planning, The hardest constraint problems: A double phase transition, Asymptotic and finite size parameters for phase transitions: Hamiltonian circuit as a case study, Downward refinement and the efficiency of hierarchical problem solving, Exploiting the deep structure of constraint problems, Easy problems are sometimes hard, Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability, A new class of hard problem instances for the 0-1 knapsack problem, Graph 3-coloring with a hybrid self-adaptive evolutionary algorithm, Completeness, approximability and exponential time results for counting problems with easy decision version, Regular-SAT: A many-valued approach to solving combinatorial problems, Modelling and solving temporal reasoning as propositional satisfiability, On Monte Carlo tree search for weighted vertex coloring, A general model and thresholds for random constraint satisfaction problems, Planning as satisfiability: heuristics, Proof of the satisfiability conjecture for large \(k\), Regular pattern-free coloring, Some computational aspects of DISTANCE SAT, A systematic study on meta-heuristic approaches for solving the graph coloring problem, Resolving Braess's paradox in random networks, Testing heuristics: We have it all wrong, Cardinal: a finite sets constraint solver, Average-case complexity of backtrack search for coloring sparse random graphs, Phase transitions and the search problem, Generating hard satisfiability problems, Experimental results on the crossover point in random 3-SAT, The satisfiability constraint gap, An empirical study of phase transitions in binary constraint satisfaction problems, Some pitfalls for experimenters with random SAT, Refining the phase transition in combinatorial search, Locating the phase transition in binary constraint satisfaction problems, A study of complexity transitions on the asymmetric traveling salesman problem, A probabilistic analysis of propositional STRIPS planning, Critical behavior in the computational cost of satisfiability testing, The TSP phase transition, Upper-bounding the \(k\)-colorability threshold by counting covers, Exploring the role of graph spectra in graph coloring algorithm performance, An upper (lower) bound for Max (Min) CSP, Discovering the suitability of optimisation algorithms by learning from evolved instances, Generalized probabilistic satisfiability and applications to modelling attackers with side-channel capabilities, Processing disjunctions in temporal constraint networks, The asymptotic \(k\)-SAT threshold, Algorithms and mechanisms for procuring services with uncertain durations using redundancy, SAT problems with chains of dependent variables, Probabilistic satisfiability: algorithms with the presence and absence of a phase transition, On the average similarity degree between solutions of random \(k\)-SAT and random CSPs., Manipulation can be hard in tractable voting systems even for constant-sized coalitions, Modelling the dynamics of stochastic local search on \(k\)-SAT, Controlled generation of hard and easy Bayesian networks: Impact on maximal clique size in tree clustering, Asynchronous aggregation and consistency in distributed constraint satisfaction, Distributed stochastic search and distributed breakout: properties, comparison and applications to constraint optimization problems in sensor networks, Algorithm runtime prediction: methods \& evaluation, Exact algorithms for maximum clique: a computational study, Multi-threading a state-of-the-art maximum clique algorithm, Visualizing SAT instances and runs of the DPLL algorithm, Constraint satisfaction -- algorithms and complexity analysis, Review on nature-inspired algorithms, Constructive generation of very hard 3-colorability instances, Generalized probabilistic satisfiability, Towards a practical engineering tool for rostering, Solving hard qualitative temporal reasoning problems: Evaluating the efficiency of using the ORD-Horn class, Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems, A wide-ranging computational comparison of high-performance graph colouring algorithms, The satisfiability threshold for random linear equations, Control complexity in Bucklin and fallback voting: an experimental analysis, Measuring instance difficulty for combinatorial optimization problems, On the phase transitions of random \(k\)-constraint satisfaction problems, Lexicographically-ordered constraint satisfaction problems, Hardness measures for gridworld benchmarks and performance analysis of real-time heuristic search algorithms, On the application of graph colouring techniques in round-robin sports scheduling, A case study in programming a quantum annealer for hard operational planning problems, Accelerating backtrack search with a best-first-search strategy, The maximum happy induced subgraph problem: bounds and algorithms, Leadership in singleton congestion games: what is hard and what is easy, On the connection between the phase transition of the covering test and the learning success rate in ILP, A general-purpose hill-climbing method for order independent minimum grouping problems: A case study in graph colouring and bin packing, Empirically-derived estimates of the complexity of labeling line drawings of polyhedral scenes, Remote Agent: to boldly go where no AI system has gone before, Random constraint satisfaction: easy generation of hard (satisfiable) instances, A complete anytime algorithm for number partitioning, Cable tree wiring -- benchmarking solvers on a real-world scheduling problem with a variety of precedence constraints, Graph coloring by multiagent fusion search, Backtracking algorithms for disjunctions of temporal constraints, Search algorithms in type theory, Algorithmic approach to the satisfactory graph partitioning problem, Complexity-theoretic models of phase transitions in search problems, Collective singleton-based consistency for qualitative constraint networks: theory and practice, Belief propagation on the random \(k\)-SAT model, GA performance distributions and randomly generated binary constraint satisfaction problems., On the complexity of unfrozen problems, A sharp threshold for the renameable-Horn and the \(q\)-Horn properties, SAT distributions with planted assignments and phase transitions between decision and optimization problems, Typical case complexity of satisfiability algorithms and the threshold phenomenon, Large hypertree width for sparse random hypergraphs, Backjump-based backtracking for constraint satisfaction problems, On market-inspired approaches to propositional satisfiability, ASSAT: computing answer sets of a logic program by SAT solvers, Configuration landscape analysis and backbone guided local search. I: Satisfiability and maximum satisfiability, On the hierarchical community structure of practical Boolean formulas, A Model for Phase Transition of Random Answer-Set Programs, GD-SAT model and crossover line, Critical Density Thresholds in Distributed Wireless Networks, Disordered systems insights on computational hardness, The phase transition in random horn satisfiability and its algorithmic implications, On the Integration of Singleton Consistencies and Look-Ahead Heuristics, The threshold for random ๐-SAT is 2^{๐}log2-๐(๐), Complexity of Coloring Random Graphs, Epsilon-transformation: exploiting phase transitions to solve combinatorial optimization problems, Problem structure heuristics and scaling behavior for genetic algorithms, Generating Difficult CNF Instances in Unexplored Constrainedness Regions, The number of satisfying assignments of random 2โSAT formulas, Random Instances of W[2-Complete Problems: Thresholds, Complexity, and Algorithms], Random logic programs: Linear model, Introduction to the dynamics of disordered systems: equilibrium and gradient descent, Features for the 0-1 knapsack problem based on inclusionwise maximal solutions, Phase transitions in theq-coloring of random hypergraphs, Hierarchical Hardness Models for SAT, What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO, Fractional Edge Cover Number of Model RB, Empirical Study of Phase Transition of Hamiltonian Cycle Problem in Random Graphs with Degrees Greater Than One, The large deviations of the whitening process in random constraint satisfaction problems, Constructing concrete hard instances of the maximum independent set problem, A sharp threshold for the phase transition of a restricted satisfiability problem for Horn clauses, Iterative state-space reduction for flexible computation, An Upper Bound on the Space Complexity of Random Formulae in Resolution, Quantum optimization, Complexity studies of a temporal constraint propagation algorithm: a statistical analysis, A physicist's approach to number partitioning, Frozen development in graph coloring, Constructing an asymptotic phase transition in random binary constraint satisfaction problems, Performance of linear-space search algorithms, Performance of linear-space search algorithms, Constraint Satisfaction, Edge-Matching Problems with Rotations, Turing Machines with Shortcuts: Efficient Attribute-Based Encryption for Bounded Functions, Optimization-Based Very Large-Scale Neighborhood Search for Generalized Assignment Problems with Location/Allocation Considerations, Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains, The replica symmetric phase of random constraint satisfaction problems, Parameterized Complexity, SAT Distributions with Phase Transitions between Decision and Optimization Problems, Walksat Stalls Well Below Satisfiability
