scientific article
From MaRDI portal
Publication:4012216
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 (only showing first 100 items - show all)
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
This page was built for publication:
