An Economics Approach to Hard Computational Problems

By Bernardo A. Huberman, Rajan M. Lukose, Tad Hogg. 1997

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Benchmark and Survey of Automated Machine Learning Frameworks (2019, background): “Some of these problem instances may be very unfavorable leading to drawn-out optimization periods (Huberman et al., 1997).”
Algorithm portfolios (2001, background): “A portfolio of algorithms is a collection of different algorithms and/or different copies of the same algorithm running on different processors [10,16].”
Algorithm Selection for Combinatorial Search Problems: A Survey (2012, methodology): “(2008), Kadioglu et al. (2010). Again there are different ways of doing this. Lazy approaches do not learn an explicit model, but use the set of training examples as a case base. For new problem instances, the closest instance or the set of n closest instances in the case base is determined and deci”
Heavy-Tailed Phenomena in Satisfiability and Constraint Satisfaction Problems (2000, background): “[30], who show how one can reduce expected performance on hard combinatorial problems by running several different heuristic algorithms in parallel in a “portfolio” approach.”
An Online Algorithm for Maximizing Submodular Functions (2008, methodology): “An algorithm portfolio [9] is a schedule for interleaving the execution of multiple (randomized) algorithms and periodically restarting them with a fresh random seed.”
Improving the search performance of SHADE using linear population size reduction (2014, background): “, these can be seen as instances of an algorithm portfolio approach [31].”
ISAC - Instance-Specific Algorithm Configuration (2010, background): “On the other hand, [18] suggested to use algorithm portfolios in a different way.”
Automated Algorithm Selection: Survey and Perspectives (2018, methodology): “One prominent approach is that of a parallel algorithm portfolio , where each algorithm from a given set A is run in parallel on a given problem instance i (see, e.g., Huberman et al., 1997; Gomes and Selman, 2001; Fukunaga, 2000).”
SATzilla: Portfolio-based Algorithm Selection for SAT (2008, background): “The term “algorithm portfolio” was introduced by Huberman, Lukose, and Hogg (1997) to describe the strategy of running several algorithms in parallel, potentially with different algorithms being assigned different amounts of CPU time.”
The Quest for Efficient Boolean Satisfiability Solvers (2002, unknown): “For example, portfolio design [47] aims at”