{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T13:14:48Z","timestamp":1762521288906,"version":"3.41.0"},"reference-count":84,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2009,6,1]],"date-time":"2009-06-01T00:00:00Z","timestamp":1243814400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-0205633"],"award-info":[{"award-number":["IIS-0205633"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["F30602-00-2-0598"],"award-info":[{"award-number":["F30602-00-2-0598"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,6]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>We propose the use of supervised machine learning to build models that predict an algorithm's runtime given a problem instance. We discuss the construction of these models and describe techniques for interpreting them to gain understanding of the characteristics that cause instances to be hard or easy. We also present two applications of our models: building algorithm portfolios that outperform their constituent algorithms, and generating test distributions that emphasize hard problems.<\/jats:p>\n          <jats:p>We demonstrate the effectiveness of our techniques in a case study of the combinatorial auction winner determination problem. Our experimental results show that we can build very accurate models of an algorithm's running time, interpret our models, build an algorithm portfolio that strongly outperforms the best single algorithm, and tune a standard benchmark suite to generate much harder problem instances.<\/jats:p>","DOI":"10.1145\/1538902.1538906","type":"journal-article","created":{"date-parts":[[2009,6,30]],"date-time":"2009-06-30T13:10:17Z","timestamp":1246367417000},"page":"1-52","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":71,"title":["Empirical hardness models"],"prefix":"10.1145","volume":"56","author":[{"given":"Kevin","family":"Leyton-Brown","sequence":"first","affiliation":[{"name":"University of British Columbia, Vancouver, British Columbia, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eugene","family":"Nudelman","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yoav","family":"Shoham","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, California"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,7,2]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1016\/S0304-3975(01)00159-1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1016\/j.jcss.2003.07.011"},{"volume-title":"AAAI: Proceedings of the AAAI Conference on Artificial Intelligence. 256--261","author":"Achlioptas D.","key":"e_1_2_1_3_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.5555\/1622519.1622535"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.5555\/518904.878881"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1145\/276698.276870"},{"unstructured":"Brewer E. 1994. Portable high-performance supercomputing: High-level platform-dependent optimization. Ph.D. dissertation Massachusetts Institute of Technology Cambridge MA.   Brewer E. 1994. Portable high-performance supercomputing: High-level platform-dependent optimization. Ph.D. dissertation Massachusetts Institute of Technology Cambridge MA.","key":"e_1_2_1_7_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1145\/209936.209946"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1111\/j.1467-8640.2005.00278.x"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1214\/ss\/1177009939"},{"volume-title":"IJCAI: Proceedings of the International Joint Conference on Artificial Intelligence. 331--337","author":"Cheeseman P.","key":"e_1_2_1_11_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1016\/j.tcs.2004.02.034"},{"doi-asserted-by":"crossref","unstructured":"Cramton P. Shoham Y. and Steinberg R. (Eds) 2006. Combinatorial Auctions. MIT Press Cambridge.   Cramton P. Shoham Y. and Steinberg R. (Eds) 2006. Combinatorial Auctions. MIT Press Cambridge.","key":"e_1_2_1_13_1","DOI":"10.7551\/mitpress\/9780262033428.001.0001"},{"volume-title":"NIPS: Proceedings of the Neural Information Processing Systems Conference.","author":"de Farias D. P.","key":"e_1_2_1_14_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1287\/ijoc.15.3.284.16077"},{"volume-title":"Proceedings of the IFIP\/IEEE International Workshop on Distributed Systems: Operations and Man- agement.","author":"Diao Y.","key":"e_1_2_1_16_1"},{"doi-asserted-by":"crossref","unstructured":"Doucet A. de Freitas N. and Gorden N. (Eds.) 2001. Sequential Monte Carlo Methods in Practice. Springer-Verlag.  Doucet A. de Freitas N. and Gorden N. (Eds.) 2001. Sequential Monte Carlo Methods in Practice. Springer-Verlag.","key":"e_1_2_1_17_1","DOI":"10.1007\/978-1-4757-3437-9"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1006\/jagm.1997.0867"},{"volume-title":"SODA: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Dubois O.","key":"e_1_2_1_19_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1214\/009053604000000067"},{"volume-title":"CP: Proceedings of the International Conference on Principles and Practice of Constraint Programming. 525--540","author":"Epstein S.","key":"e_1_2_1_21_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1016\/S0304-3975(01)00158-X"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1214\/aos\/1176347963"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1006\/jagm.1996.0016"},{"volume-title":"IJCAI: Proceedings of the International Joint Conference on Artificial Intelligence. 548--553","author":"Fujishima Y.","key":"e_1_2_1_25_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1007\/s10472-006-9036-z"},{"doi-asserted-by":"crossref","unstructured":"Gebruers C. and Guerri A. 2004. Machine learning for portfolio selection using structure at the instance level. In Principles and Practice of Constraint Programming Doctoral Consortium.  Gebruers C. and Guerri A. 2004. Machine learning for portfolio selection using structure at the instance level. In Principles and Practice of Constraint Programming Doctoral Consortium.","key":"e_1_2_1_27_1","DOI":"10.1007\/978-3-540-30201-8_73"},{"volume-title":"CPAIOR: Proceedings of the International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 380--386","author":"Gebruers C.","key":"e_1_2_1_28_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1007\/11536406_19"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.1145\/1287624.1287681"},{"volume-title":"UAI: Proceedings of the Conference on Uncertainty in Artificial Intelligence.","year":"2007","author":"Goldszmidt M.","key":"e_1_2_1_31_1"},{"volume-title":"CP: Proceedings of the International Conference on Principles and Practice of Constraint Programming.","author":"Gomes C.","key":"e_1_2_1_32_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1016\/S0004-3702(00)00081-3"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.1023\/A:1006314320276"},{"volume-title":"AAAI: Proceedings of the AAAI Conference on Artif. Intell. 221--226","author":"Gomes C. P.","key":"e_1_2_1_35_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.1145\/352871.352873"},{"volume-title":"Tech. Rep. TR-2001-8","year":"2001","author":"Gonen R.","key":"e_1_2_1_37_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_38_1","DOI":"10.1007\/s10479-007-0229-6"},{"doi-asserted-by":"crossref","unstructured":"Hastie T. Tibshirani R. and Friedman J. 2001. Elements of Statistical Learning. Springer-Verlang Berlin Germany.  Hastie T. Tibshirani R. and Friedman J. 2001. Elements of Statistical Learning. Springer-Verlang Berlin Germany.","key":"e_1_2_1_39_1","DOI":"10.1007\/978-0-387-21606-5"},{"volume-title":"AAAI: Proceedings of the AAAI Conference on Artif. Intell. 22--29","author":"Hoos H.","key":"e_1_2_1_40_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_41_1","DOI":"10.1016\/S0004-3702(99)00048-X"},{"unstructured":"Hoos H. H. and St\u00fctzle T. 2004. Stochastic Local Search: Foundations and Applications. Morgan-Kaufmann Reading.   Hoos H. H. and St\u00fctzle T. 2004. Stochastic Local Search: Foundations and Applications. Morgan-Kaufmann Reading.","key":"e_1_2_1_42_1"},{"volume-title":"UAI: Proceedings of the Conference on Uncertainty in Artif. Intell. 235--244","author":"Horvitz E.","key":"e_1_2_1_43_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_44_1","DOI":"10.1126\/science.275.5296.51"},{"doi-asserted-by":"publisher","key":"e_1_2_1_45_1","DOI":"10.1007\/11889205_17"},{"doi-asserted-by":"publisher","key":"e_1_2_1_46_1","DOI":"10.1007\/11527695_16"},{"doi-asserted-by":"publisher","key":"e_1_2_1_47_1","DOI":"10.5555\/1622591.1622594"},{"doi-asserted-by":"crossref","unstructured":"Knuth D. 1975. Estimating the efficiency of backtrack programs. Math. Comput. 29 129 121--136.  Knuth D. 1975. Estimating the efficiency of backtrack programs. Math. Comput. 29 129 121--136.","key":"e_1_2_1_48_1","DOI":"10.2307\/2005469"},{"doi-asserted-by":"publisher","key":"e_1_2_1_49_1","DOI":"10.1016\/S0004-3702(97)00043-X"},{"volume-title":"IJCAI: Proceedings of the International Joint Conference on Artificial Intelligence. 1587--1595","year":"2003","author":"Kolaitis P.","key":"e_1_2_1_50_1"},{"volume-title":"AAAI: Proceedings of the AAAI Conference on Artificial Intelligence, 305--310","author":"Korf R.","key":"e_1_2_1_51_1"},{"volume-title":"ICML: Proceedings of the International Conference on Machine Learning. 511--518","author":"Lagoudakis M.","key":"e_1_2_1_52_1"},{"volume-title":"SAT: Proceedings of the International Conference on Theory and Applications of Satisfiability Testing. 344--359","author":"Lagoudakis M.","key":"e_1_2_1_53_1"},{"volume-title":"CP: Proceedings of the International Conference on Principles and Practice of Constraint Programming. 899--903","author":"Leyton-Brown K.","key":"e_1_2_1_54_1"},{"volume-title":"IJCAI: Proceedings of the International Joint Conference on Artificial Intelligence. 1542--1543","author":"Leyton-Brown K.","key":"e_1_2_1_55_1"},{"volume-title":"CP: Proceedings of the International Conference on Principles and Practice of Constraint Programming. 556--572","author":"Leyton-Brown K.","key":"e_1_2_1_56_1"},{"key":"e_1_2_1_57_1","first-page":"479","article-title":"Empirical hardness models for combinatorial auctions. In Combinatorial Auctions. MIT Press, Cambridge","volume":"19","author":"Leyton-Brown K.","year":"2006","journal-title":"Chap."},{"doi-asserted-by":"publisher","key":"e_1_2_1_58_1","DOI":"10.1145\/352871.352879"},{"volume-title":"AAAI: Proceedings of the AAAI Conference on Artificial Intelligence. 56--61","author":"Leyton-Brown K.","key":"e_1_2_1_59_1"},{"volume-title":"AAAI: Proceedings of the AAAI Conference on Artificial Intelligence. 353--358","author":"Lobjois L.","key":"e_1_2_1_60_1"},{"doi-asserted-by":"crossref","unstructured":"Mason R. L. Gunst R. F. and Hess J. L. 2003. Statistical Design and Analysis of Experiments. Wiley-Interscience New York.  Mason R. L. Gunst R. F. and Hess J. L. 2003. Statistical Design and Analysis of Experiments. Wiley-Interscience New York.","key":"e_1_2_1_61_1","DOI":"10.1002\/0471458503"},{"doi-asserted-by":"publisher","key":"e_1_2_1_62_1","DOI":"10.1038\/22055"},{"doi-asserted-by":"publisher","key":"e_1_2_1_63_1","DOI":"10.1145\/352871.352872"},{"volume-title":"Proceedings of the International Conference on Theory and Applications of Satisfiability Testing, SAT 2004 Competition: Solver Descriptions. 13--14","author":"Nudelman E.","key":"e_1_2_1_64_1"},{"volume-title":"CP: Proceedings of the International Conference on Principles and Practice of Constraint Programming. 438--452","author":"Nudelman E.","key":"e_1_2_1_65_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_66_1","DOI":"10.1016\/S0065-2458(08)60520-3"},{"doi-asserted-by":"publisher","key":"e_1_2_1_67_1","DOI":"10.1287\/mnsc.44.8.1131"},{"volume-title":"CP: Proceedings of the International Conference on Principles and Practice of Constraint Programming. 573--586","author":"Ruan Y.","key":"e_1_2_1_68_1"},{"volume-title":"IJCAI: Proceedings of the International Joint Conference on Artificial Intelligence. 542--547","year":"1999","author":"Sandholm T.","key":"e_1_2_1_69_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_70_1","DOI":"10.1016\/S0004-3702(01)00159-X"},{"volume-title":"IJCAI: Proceedings of the International Joint Conference on Artificial Intelligence. 1102--1108","author":"Sandholm T.","key":"e_1_2_1_71_1"},{"key":"e_1_2_1_72_1","first-page":"374","article-title":"CABOB: A fast optimal algorithm for winner determination in combinatorial auctions. Manage","volume":"51","author":"Sandholm T.","year":"2005","journal-title":"Sci."},{"doi-asserted-by":"publisher","key":"e_1_2_1_73_1","DOI":"10.1023\/A:1022648800760"},{"doi-asserted-by":"publisher","key":"e_1_2_1_74_1","DOI":"10.1080\/00401706.1979.10489811"},{"doi-asserted-by":"publisher","key":"e_1_2_1_75_1","DOI":"10.1016\/0004-3702(95)00045-3"},{"volume-title":"IJCAI: Proceedings of the International Joint Conference on Artificial Intelligence. 254--259","author":"Slaney J.","key":"e_1_2_1_76_1"},{"volume-title":"AAAI: Proceedings of the AAAI Conference on Artificial Intelligence. 1197--1203","author":"Streeter M.","key":"e_1_2_1_77_1"},{"volume-title":"IJCAI: Proceedings of the International Joint Conference on Artificial Intelligence. 1173--1178","author":"Williams R.","key":"e_1_2_1_78_1"},{"volume-title":"CP: Proceedings of the International Conference on Principles and Practice of Constraint Programming","author":"Xu L.","series-title":"Lecture Notes in Computer Science","key":"e_1_2_1_79_1"},{"volume-title":"CP: Proceedings of the International Conference on Principles and Practice of Constraint Programming","author":"Xu L.","series-title":"Lecture Notes in Computer Science","key":"e_1_2_1_80_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_81_1","DOI":"10.1613\/jair.2490"},{"unstructured":"Zhang W. 1999. State-Space Search: Algorithms Complexity Extensions and Applications. Springer-Verlag Berlin Germany.  Zhang W. 1999. State-Space Search: Algorithms Complexity Extensions and Applications. Springer-Verlag Berlin Germany.","key":"e_1_2_1_82_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_83_1","DOI":"10.5555\/647488.726965"},{"volume-title":"NIPS: Proceedings of the Neural Information Processing Systems Conference.","author":"Zheng A.","key":"e_1_2_1_84_1"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1538902.1538906","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1538902.1538906","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:53Z","timestamp":1750278413000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1538902.1538906"}},"subtitle":["Methodology and a case study on combinatorial auctions"],"short-title":[],"issued":{"date-parts":[[2009,6]]},"references-count":84,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,6]]}},"alternative-id":["10.1145\/1538902.1538906"],"URL":"https:\/\/doi.org\/10.1145\/1538902.1538906","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2009,6]]},"assertion":[{"value":"2005-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-07-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}