# Difference between revisions of "2014 UnderstandingtheEmpiricalHardne"

(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

- (Leyton-Brown et al., 2014) ⇒ Kevin Leyton-Brown, Holger H. Hoos, Frank Hutter, and Lin Xu. (2014). “Understanding the Empirical Hardness of NP -complete Problems.” In: Communications of the ACM Journal, 57(5). doi:10.1145/2594413.2594424

**Subject Headings:** NP-Complete Algorithm.

## Notes

## Cited By

- http://scholar.google.com/scholar?q=%222014%22+Understanding+the+Empirical+Hardness+of+NP+-complete+Problems
- http://dl.acm.org/citation.cfm?id=2594413.2594424&preflayout=flat#citedby

## 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

;

Author | volume | Date Value | title | type | journal | titleUrl | doi | note | year | |
---|---|---|---|---|---|---|---|---|---|---|

2014 UnderstandingtheEmpiricalHardne | Kevin Leyton-Brown Holger H. Hoos Frank Hutter Lin Xu | Understanding the Empirical Hardness of NP -complete Problems | 10.1145/2594413.2594424 | 2014 |

Author | Kevin Leyton-Brown +, Holger H. Hoos +, Frank Hutter + and Lin Xu + |

doi | 10.1145/2594413.2594424 + |

title | Understanding the Empirical Hardness of NP -complete Problems + |

year | 2014 + |