2026-09-08T02:21:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26458 2026-09-05T19:44:14Z ddc:004 open_access

Online Matroid Embeddings Cristi, Andrés Dütting, Paul Kleinberg, Robert Paes Leme, Renato Patel, Neel Matroids Secretary Problem Online Algorithm We introduce the notion of an online matroid embedding, which is an algorithm for mapping an unknown matroid that is revealed in an online fashion to a larger-but-known matroid. The existence of such embedding enables a reduction from the version of the matroid secretary problem where the matroid is unknown to the version where the matroid is known in advance. We establish the existence of such an embedding for binary matroids, and use it to relate variants of the binary matroid secretary problem to each other, showing that seemingly simpler problems are in fact equivalent to seemingly harder ones (up to constant-factors). Specifically, we show this to be the case for the version of the matroid secretary problem in which the binary matroid is not known in advance, and where it is known in advance. We also show that the version with known matroid structure is equivalent to the problem where weights are not fully adversarial but drawn from a known pairwise-independent distribution. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrés Cristi and Paul Dütting and Robert Kleinberg and Renato Paes Leme and Neel Patel 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.69 urn:nbn:de:0030-drops-264585 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.69 eng https://creativecommons.org/licenses/by/4.0/legalcode