{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,14]],"date-time":"2026-09-14T22:41:43Z","timestamp":1789425703581,"version":"build-2803163510"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>In the matroid secretary problem we are given a stream of elements in random order and asked to choose a set of elements that maximizes the total value of the set, subject to being an independent set of a matroid given in advance. The difficulty comes from the assumption that decisions are irrevocable: if we choose to accept an element when it is presented by the stream, then we can never get rid of it, and if we choose not to accept it, then we cannot later add it. Babaioff, Immorlica, and Kleinberg [Proceedings of SODA'07] introduced this problem, gave O(1)-competitive algorithms for certain classes of matroids, and conjectured that every matroid admits an O(1)-competitive algorithm. However, most matroids that are known to admit an O(1)-competitive algorithm can be easily represented using graphs (e.g., graphic, cographic, and transversal matroids). In particular, there is very little known about $F$-representable matroids (the class of matroids that can be represented as elements of a vector space over a field $F$), which are one of the foundational types of matroids. Moreover, most of the known techniques are as dependent on graph theory as they are on matroid theory. We go beyond graphs by giving O(1)-competitive algorithms for regular matroids (the class of matroids that are representable over any field) and use techniques that are fundamentally matroid-theoretic rather than graph-theoretic. Our main technique is to leverage the seminal regular matroid decomposition theorem of Seymour, which gives a method for decomposing any regular matroid into matroids which are graphic, cographic, or isomorphic to a simple 10-element matroid. We show how to combine in a black-box manner any algorithms for these basic classes into an algorithm for a given regular matroid, i.e., how to respect the decomposition. In fact, this allows us to generalize beyond regular matroids to any class of matroids that admits such a decomposition into classes for which we already have good algorithms. In particular, we give an O(1)-competitive algorithm for the class of max-flow min-cut matroids, which Seymour showed can be decomposed into regular matroids and copies of the Fano matroid.<\/jats:p>","DOI":"10.1137\/13094030x","type":"journal-article","created":{"date-parts":[[2014,10,21]],"date-time":"2014-10-21T12:11:33Z","timestamp":1413893493000},"page":"1807-1830","source":"Crossref","is-referenced-by-count":25,"title":["Matroid Secretary for Regular and Decomposable Matroids"],"prefix":"10.1137","volume":"43","author":[{"given":"Michael","family":"Dinitz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guy","family":"Kortsarz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2014,10,21]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"M. Babaioff, M. Dinitz, A. Gupta, N. Immorlica, and K. Talwar,\n                      Secretary problems: weights and discounts\n                      , in Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '09, 2009, pp. 1245-1254.","DOI":"10.1137\/1.9781611973068.135"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1145\/1399589.1399596"},{"key":"atypb3","unstructured":"M. Babaioff, N. Immorlica, and R. Kleinberg,\n                      Matroids, secretary problems, and online mechanisms\n                      , in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '07, 2007, pp. 434-443."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1145\/2500121"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"S. Chakraborty and O. Lachish,\n                      Improved competitive ratio for the matroid secretary problem\n                      , in Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '12, 2012, pp. 1702-1712.","DOI":"10.1137\/1.9781611973099.135"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9457-2"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1145\/2491533.2491557"},{"key":"atypb8","first-page":"4","author":"Dynkin E. B.","year":"1963","journal-title":"Soviet Math. Dokl."},{"key":"atypb9","first-page":"218","author":"Feldman M.","year":"2011","journal-title":"Berlin"},{"key":"atypb10","unstructured":"M. Feldman, O. Svensson, and R. Zenklusen,\n                      A simple $O(\\log(\\log(\\mathrm{rank})))$-competitive algorithm for the matroid secretary problem\n                      , in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, San Diego, CA, 2015."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(81)80029-9"},{"key":"atypb12","first-page":"335","author":"Gharan S. O.","year":"2011","journal-title":"Berlin"},{"key":"atypb13","first-page":"246","author":"Gupta A.","year":"2010","journal-title":"Berlin"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"S. Im and Y. Wang,\n                      Secretary problems: Laminar matroid and interval scheduling\n                      , in Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '11, 2011, pp. 1265-1274.","DOI":"10.1137\/1.9781611973082.96"},{"key":"atypb15","first-page":"254","author":"Jaillet P.","year":"2013","journal-title":"Berlin"},{"key":"atypb16","unstructured":"R. Kleinberg,\n                      A multiple-choice secretary algorithm with applications to online auctions\n                      , in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '05, 2005, pp. 630-631."},{"key":"atypb17","first-page":"508","author":"Korula N.","year":"2009","journal-title":"Berlin"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"O. Lachish,\n                      O(log log rank) competitive-ratio for the matroid secretary problem\n                      , in Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science, FOCS '14, 2014.","DOI":"10.1109\/FOCS.2014.42"},{"key":"atypb19","first-page":"75","volume":"43","author":"Lov\u00e1sz L.","year":"2006","journal-title":"S.)"},{"key":"atypb20","unstructured":"T. Ma, B. Tang, and Y. Wang,\n                      The Simulated Greedy Algorithm for Several Submodular Matroid Secretary Problems\n                      , in 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), N. Portier and T. Wilke, eds., of Leibniz International Proceedings in Informatics (LIPIcs), ZO, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2013, pp. 478-489."},{"key":"atypb21","unstructured":"J. G. Oxley,\n                      Matroid Theory\n                      , Oxford University Press, New York, 1992."},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(77)90031-4"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(80)90075-1"},{"key":"atypb24","unstructured":"P. D. Seymour,\n                      Matroid minors\n                      , in Handbook of Combinatorics, vol. 1, R. L. Graham, M. Gr\u00f6tschel, and L. Lov\u00e1sz, eds., MIT Press, Cambridge, MA, 1995, pp. 527-550."},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"J. A. Soto,\n                      Matroid secretary problem in the random assignment model\n                      , in Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '11, 2011, pp. 1275-1284.","DOI":"10.1137\/1.9781611973082.97"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90030-4"},{"key":"atypb27","unstructured":"K. Truemper,\n                      Matroid Decomposition\n                      , Academic Press, Boston, MA, 1992."},{"key":"atypb28","first-page":"144","volume":"88","author":"Tutte W. T.","year":"1958","journal-title":"Trans. Amer. Math. Soc."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/13094030X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:37:22Z","timestamp":1787337442000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/13094030X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":28,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1137\/13094030X"],"URL":"https:\/\/doi.org\/10.1137\/13094030x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}