Bernardo A. Huberman, Rajan M. Lukose and Tad Hogg
Dynamics of Computation Group
Xerox Palo Alto Research Center
Palo Alto, CA 94304
For a reprint huberman@parc.xerox.com
@ARTICLE {,
AUTHOR = " Bernardo A. Huberman and Rajan M. Lukose and Tad Hogg",
TITLE = "An Economics Approach to Hard Computational Problems",
JOURNAL = "Science",
VOLUME = "275",
PAGES = "51-54",
MONTH = "January 3",
YEAR = "1997"}
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.
link to Science-on-Line