{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T05:39:50Z","timestamp":1740807590244,"version":"3.38.0"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T00:00:00Z","timestamp":1736899200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T00:00:00Z","timestamp":1736899200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100019180","name":"HORIZON EUROPE European Research Council","doi-asserted-by":"publisher","award":["817750"],"award-info":[{"award-number":["817750"]}],"id":[{"id":"10.13039\/100019180","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["200021_184622","817750","817750"],"award-info":[{"award-number":["200021_184622","817750","817750"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>The Matroid Secretary Conjecture is a notorious open problem in online optimization. It claims the existence of an <jats:italic>O<\/jats:italic>(1)-competitive algorithm for the Matroid Secretary Problem (MSP). Here, the elements of a weighted matroid appear one-by-one, revealing their weight at appearance, and the task is to select elements online with the goal to get an independent set of largest possible weight. <jats:italic>O<\/jats:italic>(1)-competitive MSP algorithms have so far only been obtained for restricted matroid classes and for MSP variations, including <jats:italic>Random-Assignment<\/jats:italic> MSP (RA-MSP), where an adversary fixes a number of weights equal to the ground set size of the matroid, which then get assigned randomly to the elements of the ground set. Unfortunately, these approaches heavily rely on knowing the full matroid upfront. This is an arguably undesirable requirement, and there are good reasons to believe that an approach towards resolving the MSP Conjecture should not rely on it. Thus, both Soto (SIAM Journal on Computing 42(1): 178-211, 2013.) and Oveis Gharan and Vondr\u00e1k (Algorithmica 67(4): 472-497, 2013.) raised as an open question whether RA-MSP admits an <jats:italic>O<\/jats:italic>(1)-competitive algorithm even without knowing the matroid upfront. In this work, we answer this question affirmatively. Our result makes RA-MSP the first well-known MSP variant with an <jats:italic>O<\/jats:italic>(1)-competitive algorithm that does not need to know the underlying matroid upfront and without any restriction on the underlying matroid. Our approach is based on first approximately learning the rank-density curve of the matroid, which we then exploit algorithmically.\n<\/jats:p>","DOI":"10.1007\/s10107-024-02177-x","type":"journal-article","created":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T13:48:45Z","timestamp":1736948925000},"page":"815-846","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Constant-competitiveness for random assignment Matroid secretary without knowing the Matroid"],"prefix":"10.1007","volume":"210","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3515-4953","authenticated-orcid":false,"given":"Richard","family":"Santiago","sequence":"first","affiliation":[]},{"given":"Ivan","family":"Sergeev","sequence":"additional","affiliation":[]},{"given":"Rico","family":"Zenklusen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,1,15]]},"reference":[{"key":"2177_CR1","doi-asserted-by":"publisher","unstructured":"Babaioff, M., Immorlica, N., Kleinberg, R.: Matroids, secretary problems, and online mechanisms. In: Symposium on Discrete Algorithms (SODA), pp. 434\u2013443 (2007). https:\/\/doi.org\/10.5555\/1283383.1283429","DOI":"10.5555\/1283383.1283429"},{"key":"2177_CR2","first-page":"627","volume":"4","author":"EB Dynkin","year":"1963","unstructured":"Dynkin, E.B.: The optimum choice of the instant for stopping a markov process. Sov. Math. 4, 627\u2013629 (1963)","journal-title":"Sov. Math."},{"key":"2177_CR3","doi-asserted-by":"publisher","unstructured":"Lachish, O.: $$O(\\log \\log ({{\\rm rank}}))$$ competitive ratio for the matroid secretary problem. In: 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 326\u2013335 (2014). https:\/\/doi.org\/10.1109\/FOCS.2014.42 . IEEE","DOI":"10.1109\/FOCS.2014.42"},{"issue":"2","key":"2177_CR4","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1287\/moor.2017.0876","volume":"43","author":"M Feldman","year":"2018","unstructured":"Feldman, M., Svensson, O., Zenklusen, R.: A simple $$O(\\log \\log ({{\\rm rank}}))$$-competitive algorithm for the matroid secretary problem. Math. Op. Res. 43(2), 638\u2013650 (2018). https:\/\/doi.org\/10.1287\/moor.2017.0876","journal-title":"Math. Op. Res."},{"issue":"6","key":"2177_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3212512","volume":"65","author":"M Babaioff","year":"2018","unstructured":"Babaioff, M., Immorlica, N., Kempe, D., Kleinberg, R.: Matroid secretary problems. J. ACM 65(6), 1\u201326 (2018). https:\/\/doi.org\/10.1145\/3212512","journal-title":"J. ACM"},{"key":"2177_CR6","doi-asserted-by":"publisher","unstructured":"Korula, N., P\u00e1l, M.: Algorithms for secretary problems on graphs and hypergraphs. In: Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP), pp. 508\u2013520 (2009). https:\/\/doi.org\/10.1007\/978-3-642-02930-1_42","DOI":"10.1007\/978-3-642-02930-1_42"},{"key":"2177_CR7","doi-asserted-by":"publisher","unstructured":"Im, S., Wang, Y.: Secretary problems: Laminar matroid and interval scheduling. In: Proceedings of the 22nd Annual ACM -SIAM Symposium on Discrete Algorithms (SODA), pp. 1265\u20131274 (2011). https:\/\/doi.org\/10.5555\/2133036.2133132","DOI":"10.5555\/2133036.2133132"},{"issue":"1","key":"2177_CR8","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1137\/110852061","volume":"42","author":"JA Soto","year":"2013","unstructured":"Soto, J.A.: Matroid secretary problem in the random-assignment model. SIAM J. Comput. 42(1), 178\u2013211 (2013). https:\/\/doi.org\/10.1137\/110852061","journal-title":"SIAM J. Comput."},{"key":"2177_CR9","doi-asserted-by":"publisher","unstructured":"Jaillet, P., Soto, J.A., Zenklusen, R.: Advances on matroid secretary problems: Free order model and laminar case. In: International Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 254\u2013265 (2013). https:\/\/doi.org\/10.1007\/978-3-642-36694-9_22 . Springer","DOI":"10.1007\/978-3-642-36694-9_22"},{"issue":"4","key":"2177_CR10","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1007\/s00224-015-9642-4","volume":"58","author":"T Ma","year":"2016","unstructured":"Ma, T., Tang, B., Wang, Y.: The simulated greedy algorithm for several submodular matroid secretary problems. Theor. Comp. Sys. 58(4), 681\u2013706 (2016). https:\/\/doi.org\/10.1007\/s00224-015-9642-4","journal-title":"Theor. Comp. Sys."},{"issue":"1\u20132","key":"2177_CR11","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/s00453-010-9457-2","volume":"62","author":"NB Dimitrov","year":"2012","unstructured":"Dimitrov, N.B., Plaxton, C.G.: Competitive weighted matching in transversal matroids. Algorithmica 62(1\u20132), 333\u2013348 (2012). https:\/\/doi.org\/10.1007\/s00453-010-9457-2","journal-title":"Algorithmica"},{"key":"2177_CR12","doi-asserted-by":"publisher","unstructured":"Kesselheim, T., Radke, K., T\u00f6nnis, A., V\u00f6cking, B.: An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. In: Proceedings of the 21st Annual European Symposium on Algorithms (ESA), pp. 589\u2013600 (2013). https:\/\/doi.org\/10.1007\/978-3-642-40450-4_50","DOI":"10.1007\/978-3-642-40450-4_50"},{"issue":"5","key":"2177_CR13","doi-asserted-by":"publisher","first-page":"1807","DOI":"10.1137\/13094030X","volume":"43","author":"M Dinitz","year":"2014","unstructured":"Dinitz, M., Kortsarz, G.: Matroid secretary for regular and decomposable matroids. SIAM J. Comput. 43(5), 1807\u20131830 (2014). https:\/\/doi.org\/10.1137\/13094030X","journal-title":"SIAM J. Comput."},{"issue":"4","key":"2177_CR14","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1007\/s00453-013-9795-y","volume":"67","author":"S Oveis Gharan","year":"2013","unstructured":"Oveis Gharan, S., Vondr\u00e1k, J.: On variants of the matroid secretary problem. Algorithmica 67(4), 472\u2013497 (2013). https:\/\/doi.org\/10.1007\/s00453-013-9795-y","journal-title":"Algorithmica"},{"key":"2177_CR15","doi-asserted-by":"publisher","unstructured":"Chakraborty, S., Lachish, O.: Improved competitive ratio for the matroid secretary problem. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1702\u20131712 (2012). https:\/\/doi.org\/10.1137\/1.9781611973099.135","DOI":"10.1137\/1.9781611973099.135"},{"key":"2177_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585865","author":"D Karger","year":"1998","unstructured":"Karger, D.: Random sampling and greedy sparsification for matroid optimization problems. Math. Program. (1998). https:\/\/doi.org\/10.1007\/BF01585865","journal-title":"Math. Program."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02177-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-024-02177-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02177-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T16:03:43Z","timestamp":1740758623000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-024-02177-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,15]]},"references-count":16,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["2177"],"URL":"https:\/\/doi.org\/10.1007\/s10107-024-02177-x","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2025,1,15]]},"assertion":[{"value":"17 May 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 November 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 January 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"Not applicable.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}]}}