{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:23:27Z","timestamp":1750307007822,"version":"3.41.0"},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2013,8,15]],"date-time":"2013-08-15T00:00:00Z","timestamp":1376524800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:p>We show how to find optimal algorithms for the selection of one or more order statistics over a small set of numbers, and as an extreme case, complete sorting. The criterion is using the smallest number of comparisons; separate derivations are performed for minimization on the average (over all permutations) or in the worst case. When the computational process establishes the optimal values, it also generates C-language functions that implement policies which achieve those optimal values. The search for the algorithms is driven by a Markov decision process, and the program provides the optimality proof as well.<\/jats:p>","DOI":"10.1145\/2444016.2493373","type":"journal-article","created":{"date-parts":[[2013,12,3]],"date-time":"2013-12-03T14:37:28Z","timestamp":1386081448000},"source":"Crossref","is-referenced-by-count":2,"title":["Optimal selection and sorting via dynamic programming"],"prefix":"10.1145","volume":"18","author":[{"given":"Micha","family":"Hofri","sequence":"first","affiliation":[{"name":"Worcester Polytechnic Institute, Worcester, MA"}]}],"member":"320","published-online":{"date-parts":[[2013,8,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/648257.753042"},{"key":"e_1_2_1_2_1","unstructured":"Bellman R. 1957. Dynamic Programming. Princeton University Press. (The 1972 6th printing of the book was reissued in 2003 by Dover Publications).   Bellman R. 1957. Dynamic Programming. Princeton University Press. (The 1972 6 th printing of the book was reissued in 2003 by Dover Publications)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.05.039"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02679613"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Omtet L. 1974. Advanced Combinatorics. D. Reidel Publishing.  Omtet L. 1974. Advanced Combinatorics. D. Reidel Publishing.","DOI":"10.1007\/978-94-010-2196-8"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218001404003228"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/235767.235772"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1080\/0025570X.1990.11977475"},{"volume":"479","volume-title":"Communicating Mathematics: A Conference in Honor of Joseph A. Gallian's 65th Birthday, T. Y. Chow and D. C. Isaksen, Eds., Contemporary Mathematics","author":"Hartke S. G.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","unstructured":"Knuth D. 1999. The Art of Computer Programming. Vol III: Sorting and Searching 2nd Ed. Addison-Wesley.   Knuth D. 1999. The Art of Computer Programming. Vol III: Sorting and Searching 2 nd Ed. Addison-Wesley."},{"volume-title":"Combinatorial Algorithms: Generation, Enumeration, and Search","year":"1998","author":"Kreher D.","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(74)90039-8"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/647912.740654"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Ross S. 1983. Stochastic Dynamic Programming. Academic Press.  Ross S. 1983. Stochastic Dynamic Programming. Academic Press.","DOI":"10.1016\/B978-0-12-598420-1.50006-4"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2444016.2493373","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2444016.2493373","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:48:57Z","timestamp":1750236537000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2444016.2493373"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,8,15]]},"references-count":14,"alternative-id":["10.1145\/2444016.2493373"],"URL":"https:\/\/doi.org\/10.1145\/2444016.2493373","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2013,8,15]]}}}