{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:15:43Z","timestamp":1763468143697,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2013,6,3]],"date-time":"2013-06-03T00:00:00Z","timestamp":1370217600000},"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":["SIGACT News"],"published-print":{"date-parts":[[2013,6,3]]},"abstract":"<jats:p>The matroid secretary problem was introduced by Babaioff, Immorlica, and Kleinberg in SODA 2007 as an online problem that was both mathematically interesting and had applications to online auctions. In this column I will introduce and motivate this problem, and give a survey of some of the exciting work that has been done on it over the past 6 years. While we have a much better understanding of matroid secretary now than we did in 2007, the main conjecture is still open: does there exist an O(1)-competitive algorithm.<\/jats:p>","DOI":"10.1145\/2491533.2491557","type":"journal-article","created":{"date-parts":[[2013,6,5]],"date-time":"2013-06-05T12:09:34Z","timestamp":1370434174000},"page":"126-142","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Recent advances on the matroid secretary problem"],"prefix":"10.1145","volume":"44","author":[{"given":"Michael","family":"Dinitz","sequence":"first","affiliation":[{"name":"Weizmann Institute of Science"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,6,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496905"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1886521.1886526"},{"key":"e_1_2_1_3_1","first-page":"434","volume-title":"Proc. SODA","author":"Babaioff Moshe","year":"2007"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1399589.1399596"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095251"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.8"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_33"},{"key":"e_1_2_1_8_1","first-page":"4","article-title":"The optimum choice of the instant for stopping a markov process","author":"Dynkin E. B.","year":"1963","journal-title":"Soviet Math. Dokl"},{"key":"e_1_2_1_9_1","first-page":"69","volume-title":"Calgary Internat. Conf.)","author":"Edmonds Jack","year":"1970"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1214\/ss\/1177012493"},{"key":"e_1_2_1_11_1","first-page":"218","volume-title":"Proc. APPROX\/RANDOM","author":"Feldman Moran","year":"2011"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.2307\/1402748"},{"key":"e_1_2_1_13_1","first-page":"246","volume-title":"Proc. WINE","author":"Gupta Anupam","year":"2010"},{"key":"e_1_2_1_14_1","first-page":"335","volume-title":"Proc. ESA","author":"Gharan Shayan Oveis","year":"2011"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133132"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36694-9_22"},{"key":"e_1_2_1_17_1","first-page":"630","volume-title":"Proc. SODA","author":"Kleinberg Robert","year":"2005"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02930-1_42"},{"volume-title":"Dover Publications","year":"1987","author":"Mosteller Frederick","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","first-page":"478","volume-title":"Yajun Wang. The Simulated Greedy Algorithm for Several Submodular Matroid Secretary Problems. In Proc. STACS","author":"Ma Tengyu","year":"2013"},{"volume-title":"Oxford Graduate Texts in Mathematics Series","year":"1992","author":"Oxley J.G.","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(80)90075-1"},{"volume-title":"MIT Press","year":"1995","author":"Seymour P. D.","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133133"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.2307\/2371182"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2491533.2491557","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2491533.2491557","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:28:50Z","timestamp":1750231730000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2491533.2491557"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6,3]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,6,3]]}},"alternative-id":["10.1145\/2491533.2491557"],"URL":"https:\/\/doi.org\/10.1145\/2491533.2491557","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2013,6,3]]},"assertion":[{"value":"2013-06-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}