{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:40:13Z","timestamp":1767339613917,"version":"3.41.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2018,11,19]],"date-time":"2018-11-19T00:00:00Z","timestamp":1542585600000},"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":["J. ACM"],"published-print":{"date-parts":[[2018,12,31]]},"abstract":"<jats:p>\n            We define a generalization of the classical secretary problem called the\n            <jats:italic>matroid secretary problem<\/jats:italic>\n            . In this problem, the elements of a matroid are presented to an online algorithm in uniformly random order. When an element arrives, the algorithm observes its value and must make an irrevocable decision whether or not to accept it. The accepted elements must form an independent set, and the objective is to maximize the combined value of these elements. We present an\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>k<\/jats:italic>\n            )-competitive algorithm for general matroids (where\n            <jats:italic>k<\/jats:italic>\n            is the rank of the matroid), and constant-competitive algorithms for several special cases including graphic matroids, truncated partition matroids, and bounded degree transversal matroids. We leave as an open question the existence of constant-competitive algorithms for general matroids. Our results have applications in welfare-maximizing online mechanism design for domains in which the sets of simultaneously satisfiable agents form a matroid.\n          <\/jats:p>","DOI":"10.1145\/3212512","type":"journal-article","created":{"date-parts":[[2018,11,20]],"date-time":"2018-11-20T14:19:23Z","timestamp":1542723563000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":24,"title":["Matroid Secretary Problems"],"prefix":"10.1145","volume":"65","author":[{"given":"Moshe","family":"Babaioff","sequence":"first","affiliation":[{"name":"Microsoft Research, Herzliya, Israel"}]},{"given":"Nicole","family":"Immorlica","sequence":"additional","affiliation":[{"name":"Microsoft Research, MA, USA"}]},{"given":"David","family":"Kempe","sequence":"additional","affiliation":[{"name":"University of Southern California, CA, USA"}]},{"given":"Robert","family":"Kleinberg","sequence":"additional","affiliation":[{"name":"Cornell University, NY, USA"}]}],"member":"320","published-online":{"date-parts":[[2018,11,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/130949191"},{"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","volume-title":"Proc. 18th ACM Symp. on Discrete Algorithms. 434--443","author":"Babaioff Moshe","year":"2007","unstructured":"Moshe Babaioff , Nicole Immorlica , and Robert Kleinberg . 2007 a. Matroids, secretary problems, and online mechanisms . In Proc. 18th ACM Symp. on Discrete Algorithms. 434--443 . Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. 2007a. Matroids, secretary problems, and online mechanisms. In Proc. 18th ACM Symp. on Discrete Algorithms. 434--443."},{"key":"e_1_2_1_4_1","volume-title":"Proc. 20th AAAI Conf. on Artificial Intelligence. 241--247","author":"Babaioff Moshe","year":"2005","unstructured":"Moshe Babaioff , Ron Lavi , and Elan Pavlov . 2005 . Mechanism design for single-value domains . In Proc. 20th AAAI Conf. on Artificial Intelligence. 241--247 . Moshe Babaioff, Ron Lavi, and Elan Pavlov. 2005. Mechanism design for single-value domains. In Proc. 20th AAAI Conf. on Artificial Intelligence. 241--247."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_7"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1886521.1886526"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13036-6_13"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095251"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9457-2"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491533.2491557"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/13094030X"},{"key":"e_1_2_1_12_1","volume-title":"Dubhashi and Alessandro Panconesi","author":"Devdatt","year":"2009","unstructured":"Devdatt P. Dubhashi and Alessandro Panconesi . 2009 . Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press . Devdatt P. Dubhashi and Alessandro Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press."},{"key":"e_1_2_1_13_1","first-page":"627","article-title":"The optimum choice of the instant for stopping a Markov process","volume":"4","author":"Dynkin Eugene B.","year":"1963","unstructured":"Eugene B. Dynkin . 1963 . The optimum choice of the instant for stopping a Markov process . Sov. Math. Dokl. 4 (1963), 627 -- 629 . Eugene B. Dynkin. 1963. The optimum choice of the instant for stopping a Markov process. Sov. Math. Dokl. 4 (1963), 627--629.","journal-title":"Sov. Math. Dokl."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/2033252.2033272"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722208"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229053"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.37"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.2307\/1402748"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1940179.1940200"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/988772.988784"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133132"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/11944874_35"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36694-9_22"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585865"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746602"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40450-4_50"},{"key":"e_1_2_1_27_1","unstructured":"Thomas Kesselheim and Andreas T\u00f6nnis. 2016. Submodular Secretary Problems: Cardinality Matching and Linear Constraints. Retrieved from http:\/\/arxiv.org\/abs\/1607.08805 CoRR abs\/1607.08805.  Thomas Kesselheim and Andreas T\u00f6nnis. 2016. Submodular Secretary Problems: Cardinality Matching and Linear Constraints. Retrieved from http:\/\/arxiv.org\/abs\/1607.08805 CoRR abs\/1607.08805."},{"key":"e_1_2_1_28_1","volume-title":"Proc. 16th ACM Symp. on Discrete Algorithms. 630--631","author":"Kleinberg Robert D.","year":"2005","unstructured":"Robert D. Kleinberg . 2005 . A multiple-choice secretary problem with applications to online auctions . In Proc. 16th ACM Symp. on Discrete Algorithms. 630--631 . Robert D. Kleinberg. 2005. A multiple-choice secretary problem with applications to online auctions. In Proc. 16th ACM Symp. on Discrete Algorithms. 630--631."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213991"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02930-1_42"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993582"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.42"},{"key":"e_1_2_1_33_1","volume-title":"Proc. 16th ACM Symp. on Discrete Algorithms. 1146--1155","author":"Lavi Ron","year":"2005","unstructured":"Ron Lavi and Noam Nisan . 2005 . Online ascending auctions for gradually expiring items . In Proc. 16th ACM Symp. on Discrete Algorithms. 1146--1155 . Ron Lavi and Noam Nisan. 2005. Online ascending auctions for gradually expiring items. In Proc. 16th ACM Symp. on Discrete Algorithms. 1146--1155."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585266"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-015-9642-4"},{"volume-title":"Randomized Algorithms","author":"Motwani Rajeev","key":"e_1_2_1_36_1","unstructured":"Rajeev Motwani and Prabhakar Raghavan . 1995. Randomized Algorithms . Cambridge University Press . Rajeev Motwani and Prabhakar Raghavan. 1995. Randomized Algorithms. Cambridge University Press."},{"key":"e_1_2_1_37_1","volume-title":"Proc. 17th AAAI Conf. on Artificial Intelligence. 379--384","author":"Mu\u2019alem Ahuva","year":"2002","unstructured":"Ahuva Mu\u2019alem and Noam Nisan . 2002 . Truthful approximation mechanisms for restricted combinatorial auctions . In Proc. 17th AAAI Conf. on Artificial Intelligence. 379--384 . Ahuva Mu\u2019alem and Noam Nisan. 2002. Truthful approximation mechanisms for restricted combinatorial auctions. In Proc. 17th AAAI Conf. on Artificial Intelligence. 379--384."},{"key":"e_1_2_1_38_1","volume-title":"Proc. 19th European Symp. on Algorithms. 335--346","author":"Gharan Shayan Oveis","year":"2011","unstructured":"Shayan Oveis Gharan and Jan Vondr\u00e1k . 2011 . On variants of the matroid secretary problem . In Proc. 19th European Symp. on Algorithms. 335--346 . Shayan Oveis Gharan and Jan Vondr\u00e1k. 2011. On variants of the matroid secretary problem. In Proc. 19th European Symp. on Algorithms. 335--346."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897540"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039796"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/110852061"},{"key":"e_1_2_1_42_1","volume-title":"Proc. 32nd Annual Symp. on Theoretical Aspects of Computer Science. 716--729","author":"Vardi Shai","year":"2015","unstructured":"Shai Vardi . 2015 . The returning secretary . In Proc. 32nd Annual Symp. on Theoretical Aspects of Computer Science. 716--729 . Shai Vardi. 2015. The returning secretary. In Proc. 32nd Annual Symp. on Theoretical Aspects of Computer Science. 716--729."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3212512","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3212512","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:54:16Z","timestamp":1750287256000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3212512"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,19]]},"references-count":42,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2018,12,31]]}},"alternative-id":["10.1145\/3212512"],"URL":"https:\/\/doi.org\/10.1145\/3212512","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2018,11,19]]},"assertion":[{"value":"2016-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}