Laminar Matroid Secretary: Greedy Strikes Back

Autor:	Huang, Zhiyi, Parsaeian, Zahra, Zhu, Zixuan
Rok vydání:	2023
Předmět:	Computer Science - Data Structures and Algorithms Computer Science - Computer Science and Game Theory
Druh dokumentu:	Working Paper
Popis:	We show that a simple greedy algorithm is $4.75$ probability-competitive for the Laminar Matroid Secretary Problem, improving the $3\sqrt{3} \approx 5.196$-competitive algorithm based on the forbidden sets technique (Soto, Turkieltaub, and Verdugo, 2018).
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2308.09880 Zobrazit plný text záznamu View this record from Arxiv