{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T07:52:26Z","timestamp":1780732346947,"version":"3.54.1"},"reference-count":12,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T00:00:00Z","timestamp":1259625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGecom Exch."],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:p>\n            In the classical secretary problem an employer would like to choose the best candidate among\n            <jats:italic>n<\/jats:italic>\n            competing candidates that arrive in a random order. Our main contribution is a new linear programming technique that we introduce as a tool for obtaining and analyzing mechanisms for the secretary problem and its variants. The linear program is formulated using judiciously chosen variables and constraints and we show a one-to-one correspondence between mechanisms for the secretary problem and feasible solutions to the linear program.\n          <\/jats:p>","DOI":"10.1145\/1980522.1980528","type":"journal-article","created":{"date-parts":[[2011,5,17]],"date-time":"2011-05-17T12:59:03Z","timestamp":1305637143000},"page":"1-5","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Secretary problems and incentives via linear programming"],"prefix":"10.1145","volume":"8","author":[{"given":"Niv","family":"Buchbinder","sequence":"first","affiliation":[{"name":"Microsoft Research, New England"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kamal","family":"Jain","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohit","family":"Singh","sequence":"additional","affiliation":[{"name":"Microsoft Research, New England"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2009,12]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"SODA '09: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics","author":"Babaioff M.","unstructured":"Babaioff , M. , Dinitz , M. , Gupta , A. , Immorlica , N. , and Talwar , K . 2009. Secretary problems: weights and discounts . In SODA '09: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics , Philadelphia, PA, USA, 1245--1254. Babaioff, M., Dinitz, M., Gupta, A., Immorlica, N., and Talwar, K. 2009. Secretary problems: weights and discounts. In SODA '09: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1245--1254."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74208-1_2"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1399589.1399596"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings 18th ACM-SIAM Symposium on Discrete Algorithms.","author":"Babaioff M.","unstructured":"Babaioff , M. , Immorlica , N. , and Kleinberg , R . 2007. Matroids, Secretary Problems, and Online Mechanisms . In Proceedings 18th ACM-SIAM Symposium on Discrete Algorithms. Babaioff, M., Immorlica, N., and Kleinberg, R. 2007. Matroids, Secretary Problems, and Online Mechanisms. In Proceedings 18th ACM-SIAM Symposium on Discrete Algorithms."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Buchbinder N. Singh M. and Jain K. 2009a. Incentives in Online Auctions and Secretary Problems via Linear Programming. In Manuscript.  Buchbinder N. Singh M. and Jain K. 2009a. Incentives in Online Auctions and Secretary Problems via Linear Programming. In Manuscript .","DOI":"10.1007\/978-3-642-17572-5_9"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Buchbinder N. Singh M. and Jain K. 2009b. Secretary Problems via Linear Programming. In Manuscript.  Buchbinder N. Singh M. and Jain K. 2009b. Secretary Problems via Linear Programming. In Manuscript .","DOI":"10.1007\/978-3-642-13036-6_13"},{"key":"e_1_2_1_7_1","unstructured":"Dynkin E. B. 1963. The Optimum Choice of the Instant for Stopping a Markov Process. Sov. Math. Dokl. 4.  Dynkin E. B. 1963. The Optimum Choice of the Instant for Stopping a Markov Process. Sov. Math. Dokl. 4 ."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1214\/ss\/1177012493"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/988772.988784"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete algorithms.","author":"Kleinberg R.","year":"2005","unstructured":"Kleinberg , R. 2005 . A Multiple-Choice Secretary Algorithm with Applications to Online Auctions . In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete algorithms. Kleinberg, R. 2005. A Multiple-Choice Secretary Algorithm with Applications to Online Auctions. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete algorithms."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02930-1_42"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.2307\/2985407"}],"container-title":["ACM SIGecom Exchanges"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1980522.1980528","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1980522.1980528","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:52Z","timestamp":1750278172000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1980522.1980528"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":12,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,12]]}},"alternative-id":["10.1145\/1980522.1980528"],"URL":"https:\/\/doi.org\/10.1145\/1980522.1980528","relation":{},"ISSN":["1551-9031"],"issn-type":[{"value":"1551-9031","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12]]},"assertion":[{"value":"2009-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}