An Economics Approach to Hard Computational Problems

3 January 1997

journal article
other
Published by American Association for the Advancement of Science (AAAS) in Science

Vol. 275 (5296) , 51-54
https://doi.org/10.1126/science.275.5296.51

Abstract

A general method for combining existing algorithms into new programs that are unequivocally preferable to any of the component algorithms is presented. This method, based on notions of risk in economics, offers a computational portfolio design procedure that can be used for a wide range of problems. Tested by solving a canonical NP-complete problem, the method can be used for problems ranging from the combinatorics of DNA sequencing to the completion of tasks in environments with resource contention, such as the World Wide Web.

Keywords

This publication has 7 references indexed in Scilit:

Phase transitions and the search problem
Artificial Intelligence, 1996
The satisfiability constraint gap
Artificial Intelligence, 1996
Randomized Algorithms
Published by Cambridge University Press (CUP) ,1995
Critical Behavior in the Satisfiability of Random Boolean Expressions
Science, 1994
Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems
Artificial Intelligence, 1992
Cooperative Solution of Constraint Satisfaction Problems
Science, 1991
Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
Operations Research, 1991