An economics approach to hard computational problems

被引：217

作者：

Huberman, BA

Lukose, RM

Hogg, T

机构：

[1] Dynamics of Computation Group, Xerox Palo Alto Research Center, Palo Alto

来源：

SCIENCE | 1997年 / 275卷 / 5296期

关键词：

D O I：

10.1126/science.275.5296.51

中图分类号：

O [数理科学和化学]; P [天文学、地球科学]; Q [生物科学]; N [自然科学总论];

学科分类号：

07 ; 0710 ; 09 ;

摘要：

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.

引用

页码：51 / 54

页数：4

共 26 条

[1]

ALDOUS D, 1994, AN S FDN CO, P492, DOI 10.1109/SFCS.1994.365742

[2]

ALIZADEH F, 1994, 5TH P ANN ACM SIAM S, P489

[3]

Alt H., 1991, TR91057 INT COMP SCI

[4]

BOYER M, IN PRESS P WORKSH PH

[5]

CESABIANCHI N, 1993, 25TH P ANN ACM S THE, P382

[6] COOPERATIVE SOLUTION OF CONSTRAINT SATISFACTION PROBLEMS [J].

CLEARWATER, SH ;

HUBERMAN, BA ;

HOGG, T .

SCIENCE, 1991, 254 (5035) :1181-1183

[7]

ERTEL W, 1992, LECT NOTES ARTIF INT, V590, P195

[8]

Garey M., 1970, COMPUTERS INTRACTABI

[9] The satisfiability constraint gap [J].

Gent, IP ;

Walsh, T .

ARTIFICIAL INTELLIGENCE, 1996, 81 (1-2) :59-80

[10]

Grover L. K., 1996, P 28 ANN ACM S THEOR

← 1 2 3 →