Empirical hardness models
Abstract
Is it possible to predict how long an algorithm will take to solve a previously-unseen instance of an NP-complete problem? If so, what uses can be found for models that make such predictions? This article provides answers to these questions and evaluates the answers experimentally.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jun 01, 2009
- Source ID
- 10.1145/1538902.1538906
Entities
People
- Eugene Nudelman
- Kevin Leyton-brown
- Yoav Shoham
Organizations
- Defense Advanced Research Projects Agency
- Division of Information and Intelligent Systems
- Stanford University
- University of British Columbia