Text
Strong Algorithms for the Ordinal Matroid Secretary Problem
In the ordinal matroid secretary problem (MSP), candidates do not reveal numerical weights, but the decision maker can still discern if a candidate is better than another. An algorithm α is probability-competitive if every element from the optimum appears with probability 1/α in the output. This measure is stronger than the standard utility competitiveness. Our main result is the introduction of a technique based on forbidden sets to design algorithms with strong probability-competitive ratios on many matroid classes. We improve upon the guarantees for almost every matroid class considered in the MSP literature. In particular, we achieve probability-competitive ratios of 4 for graphic matroids and of 33–√≈5.19 for laminar matroids. Additionally, we modify Kleinberg’s 1+O(1/ρ) utility-competitive algorithm for uniform matroids of rank ρ in order to obtain a 1+O(logρ/ρ−−−−−−√) probability-competitive algorithm. We also contribute algorithms for the ordinal MSP on arbitrary matroids.
Barcode | Tipe Koleksi | Nomor Panggil | Lokasi | Status | |
---|---|---|---|---|---|
art139696 | null | Artikel | Gdg9-Lt3 | Tersedia namun tidak untuk dipinjamkan - No Loan |
Tidak tersedia versi lain