Difference between revisions of "2014 UnderstandingtheEmpiricalHardne"

From GM-RKB
Jump to: navigation, search
(ContinuousReplacement)
(Tag: continuous replacement)
m (Text replacement - " Yoav Shoham" to " Yoav Shoham")
 
Line 57: Line 57:
 
* 25. Knuth, D. Estimating the Efficiency of Backtrack Programs. <i>Mathematics of Computation 29</i>, 129 (1975), 121--136.
 
* 25. Knuth, D. Estimating the Efficiency of Backtrack Programs. <i>Mathematics of Computation 29</i>, 129 (1975), 121--136.
 
* 26. Leyton-Brown, K., Nudelman, E., Andrew, G., McFadden, J. and Shoham. Boosting As a Metaphor for Algorithm Design. In <i>Proceedings for Principles and Practice of Constraint Programming</i> (2003), 899--903.
 
* 26. Leyton-Brown, K., Nudelman, E., Andrew, G., McFadden, J. and Shoham. Boosting As a Metaphor for Algorithm Design. In <i>Proceedings for Principles and Practice of Constraint Programming</i> (2003), 899--903.
* 27. Kevin Leyton-Brown, Eugene Nudelman, Galen Andrew, Jim McFadden, Yoav Shoham, A Portfolio Approach to Algorithm Select, Proceedings of the 18th International Joint Conference on Artificial Intelligence, p.1542-1543, August 09-15, 2003, Acapulco, Mexico
+
* 27. Kevin Leyton-Brown, Eugene Nudelman, Galen Andrew, Jim McFadden, [[Yoav Shoham]], A Portfolio Approach to Algorithm Select, Proceedings of the 18th International Joint Conference on Artificial Intelligence, p.1542-1543, August 09-15, 2003, Acapulco, Mexico
* 28. Kevin Leyton-Brown, Eugene Nudelman, Yoav Shoham, Learning the Empirical Hardness of Optimization Problems: The Case of Combinatorial Auctions, Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, p.556-572, September 09-13, 2002
+
* 28. Kevin Leyton-Brown, Eugene Nudelman, [[Yoav Shoham]], Learning the Empirical Hardness of Optimization Problems: The Case of Combinatorial Auctions, Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, p.556-572, September 09-13, 2002
* 29. Kevin Leyton-Brown, Eugene Nudelman, Yoav Shoham, Empirical Hardness Models: Methodology and a Case Study on Combinatorial Auctions, Journal of the ACM (JACM), v.56 n.4, p.1-52, June 2009 [http://doi.acm.org/10.1145/1538902.1538906 doi:10.1145/1538902.1538906]
+
* 29. Kevin Leyton-Brown, Eugene Nudelman, [[Yoav Shoham]], Empirical Hardness Models: Methodology and a Case Study on Combinatorial Auctions, Journal of the ACM (JACM), v.56 n.4, p.1-52, June 2009 [http://doi.acm.org/10.1145/1538902.1538906 doi:10.1145/1538902.1538906]
* 30. Kevin Leyton-Brown, Mark Pearson, Yoav Shoham, Towards a Universal Test Suite for Combinatorial Auction Algorithms, Proceedings of the 2nd ACM Conference on Electronic Commerce, p.66-76, October 17-20, 2000, Minneapolis, Minnesota, USA [http://doi.acm.org/10.1145/352871.352879 doi:10.1145/352871.352879]
+
* 30. Kevin Leyton-Brown, Mark Pearson, [[Yoav Shoham]], Towards a Universal Test Suite for Combinatorial Auction Algorithms, Proceedings of the 2nd ACM Conference on Electronic Commerce, p.66-76, October 17-20, 2000, Minneapolis, Minnesota, USA [http://doi.acm.org/10.1145/352871.352879 doi:10.1145/352871.352879]
 
* 31. David Mitchell, Bart Selman, Hector Levesque, Hard and Easy Distributions of SAT Problems, Proceedings of the Tenth National Conference on Artificial Intelligence, p.459-465, July 12-16, 1992, San Jose, California
 
* 31. David Mitchell, Bart Selman, Hector Levesque, Hard and Easy Distributions of SAT Problems, Proceedings of the Tenth National Conference on Artificial Intelligence, p.459-465, July 12-16, 1992, San Jose, California
 
* 32. Nudelman, E., Leyton-Brown, K., Andrew, G., Gomes, C., McFadden, J., Selman, B. and Shoham, Y. Satzilla 0.9. Solver Description. SAT Competition, 2003.
 
* 32. Nudelman, E., Leyton-Brown, K., Andrew, G., Gomes, C., McFadden, J., Selman, B. and Shoham, Y. Satzilla 0.9. Solver Description. SAT Competition, 2003.

Latest revision as of 14:37, 13 August 2019

Subject Headings: NP-Complete Algorithm.

Notes

Cited By

Quotes

Abstract

Using machine learning to predict algorithm runtime.

Introduction

Problems are intractable when they "can be solved, but not fast enough for the solution to be usable."13 NP-complete problems are commonly said to be intractable; however, the reality is more complex. All known algorithms for solving NP-complete problems require exponential time in the worst case; however, these algorithms nevertheless solve many problems of practical importance astoundingly quickly, and are hence relied upon in a broad range of applications. The propositional satisfiability problem (SAT) serves as a good example. One of the most popular approaches for the formal verification of hardware and software relies on general-purpose SAT solvers and SAT encodings, typically with hundreds of thousands of variables. These instances can often be solved in seconds, even though the same solvers can be stymied by handcrafted instances involving only hundreds of variables.

Clearly, we could benefit from a more nuanced understanding of algorithm behavior than is offered by asymptotic, worst-case analysis. Our work asks the question most relevant to an end user: " How hard is it to solve a given family of problem instances, using the best available methods? “Formal, complexity-theoretic analysis of this question seems hopeless: the best available algorithms are highly complex (and, in some cases, only available in compiled form), and instance distributions representative of practical applications are heterogeneous and richly structured. For this reason, we turn to statistical, rather than combinatorial, analysis.

...

References

;

 AuthorvolumeDate ValuetitletypejournaltitleUrldoinoteyear
2014 UnderstandingtheEmpiricalHardneKevin Leyton-Brown
Holger H. Hoos
Frank Hutter
Lin Xu
Understanding the Empirical Hardness of NP -complete Problems10.1145/2594413.25944242014
AuthorKevin Leyton-Brown +, Holger H. Hoos +, Frank Hutter + and Lin Xu +
doi10.1145/2594413.2594424 +
titleUnderstanding the Empirical Hardness of NP -complete Problems +
year2014 +