pipette
ESEspañol

A Refined Analysis for Matroid Secretary with Submodular Objectives

Dennis Joyce

Preprint

In the authors' words

We study the matroid secretary problem with a nonnegative monotone submodular objective. Elements arrive in uniformly random order, and every acceptance decision is immediate and irrevocable. We give an -competitive algorithm for arbitrary matroids. The algorithm first rejects a randomly sized initial segment of the arrival sequence as a learning set and runs submodular greedy on all elements in this set. Each later element receives a fixed weight equal to the marginal value it would have when inserted into the stored greedy sequence. On these fixed weights, the algorithm runs a linear-objective matroid secretary subroutine. The algorithm uses value queries and independence queries, where is the matroid rank.

Main resultLimitation the authors admit

Appeared: Friday, October 9. arXiv. Preprint, not yet peer-reviewed.