pipette
ENEnglish

A Refined Analysis for Matroid Secretary with Submodular Objectives

Dennis Joyce

Preprint

En palabras de los autores

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.

Resultado principalLimitación que admiten los autores

Apareció: viernes, 9 de octubre. arXiv. Preprint, todavía sin revisión por pares.