Beating Competitive Ratio 4 for Graphic Matroid Secretary
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916567414996992 |
|---|---|
| author | Banihashem, Kiarash Hajiaghayi, MohammadTaghi Kowalski, Dariusz R. Krysta, Piotr Mittal, Danny Olkowski, Jan |
| author_facet | Banihashem, Kiarash Hajiaghayi, MohammadTaghi Kowalski, Dariusz R. Krysta, Piotr Mittal, Danny Olkowski, Jan |
| contents | One of the classic problems in online decision-making is the *secretary problem* where to goal is to maximize the probability of choosing the largest number from a randomly ordered sequence. A natural extension allows selecting multiple values under a combinatorial constraint. Babaioff, Immorlica, Kempe, and Kleinberg (SODA'07, JACM'18) introduced the *matroid secretary conjecture*, suggesting an $O(1)$-competitive algorithm exists for matroids. Many works since have attempted to obtain algorithms for both general matroids and specific classes of matroids. The ultimate goal is to obtain an $e$-competitive algorithm, and the *strong matroid secretary conjecture* states that this is possible for general matroids.
A key class of matroids is the *graphic matroid*, where a set of graph edges is independent if it contains no cycle. The rich combinatorial structure of graphs makes them a natural first step towards solving a problem for general matroids. Babaioff et al. (SODA'07, JACM'18) first studied the graphic matroid setting, achieving a $16$-competitive algorithm. Subsequent works have improved the competitive ratio, most recently to 4 by Soto, Turkieltaub, and Verdugo (SODA'18).
We break this $4$-competitive barrier, presenting a new algorithm with a competitive ratio of $3.95$. For simple graphs, we further improve this to $3.77$. Intuitively, solving the problem for simple graphs is easier since they lack length-two cycles. A natural question is whether a ratio arbitrarily close to $e$ can be achieved by assuming sufficiently large girth.
We answer this affirmatively, showing a competitive ratio arbitrarily close to $e$ even for constant girth values, supporting the strong matroid secretary conjecture. We also prove this bound is tight: for any constant $g$, no algorithm can achieve a ratio better than $e$ even when the graph has girth at least $g$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_08846 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Beating Competitive Ratio 4 for Graphic Matroid Secretary Banihashem, Kiarash Hajiaghayi, MohammadTaghi Kowalski, Dariusz R. Krysta, Piotr Mittal, Danny Olkowski, Jan Data Structures and Algorithms One of the classic problems in online decision-making is the *secretary problem* where to goal is to maximize the probability of choosing the largest number from a randomly ordered sequence. A natural extension allows selecting multiple values under a combinatorial constraint. Babaioff, Immorlica, Kempe, and Kleinberg (SODA'07, JACM'18) introduced the *matroid secretary conjecture*, suggesting an $O(1)$-competitive algorithm exists for matroids. Many works since have attempted to obtain algorithms for both general matroids and specific classes of matroids. The ultimate goal is to obtain an $e$-competitive algorithm, and the *strong matroid secretary conjecture* states that this is possible for general matroids. A key class of matroids is the *graphic matroid*, where a set of graph edges is independent if it contains no cycle. The rich combinatorial structure of graphs makes them a natural first step towards solving a problem for general matroids. Babaioff et al. (SODA'07, JACM'18) first studied the graphic matroid setting, achieving a $16$-competitive algorithm. Subsequent works have improved the competitive ratio, most recently to 4 by Soto, Turkieltaub, and Verdugo (SODA'18). We break this $4$-competitive barrier, presenting a new algorithm with a competitive ratio of $3.95$. For simple graphs, we further improve this to $3.77$. Intuitively, solving the problem for simple graphs is easier since they lack length-two cycles. A natural question is whether a ratio arbitrarily close to $e$ can be achieved by assuming sufficiently large girth. We answer this affirmatively, showing a competitive ratio arbitrarily close to $e$ even for constant girth values, supporting the strong matroid secretary conjecture. We also prove this bound is tight: for any constant $g$, no algorithm can achieve a ratio better than $e$ even when the graph has girth at least $g$. |
| title | Beating Competitive Ratio 4 for Graphic Matroid Secretary |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2501.08846 |