Settling the Matroid Secretary Problem
En palabras de los autores
This paper settles the Matroid Secretary Problem with an -probability-competitive algorithm. The algorithm is ordinal and accesses arrived elements only through comparison and independence oracles, and has expected polynomial time and oracle complexity.
Resultado principalEl resumen no menciona limitaciones.
Apareció: lunes, 28 de septiembre. arXiv. Preprint, todavía sin revisión por pares.