Online Matroid Embeddings

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...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-07
Main Authors: Cristi, Andrés, Dütting, Paul, Kleinberg, Robert, Renato Paes Leme
Format: Article
Language:English
Subjects:
Algorithms
Embedding
Lower bounds
Upper bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 show that online matroid embeddings exist for binary (and hence graphic) and laminar matroids. We also show a negative result showing that no online matroid embedding exists for the class of all matroids. Finally, we define the notion of an approximate matroid embedding, generalizing the notion of {\alpha}-partition property, and provide an upper bound on the approximability of binary matroids by a partition matroid, matching the lower bound of Dughmi et al.
ISSN:2331-8422