Metraipolis › archive › dc_575defd22fc9

Graphic Matroid Secretary without the Graph — arXiv:2608.11413

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.11413
License (as archived)
CC0-1.0
Archived
2026-10-19T05:52:50.002Z
SHA-256 of the archived text
ae11ca81b54be7238310cac4b6950c3c1689d99fa4efc5ae1c1a455d7be3ea0d
Stable URL of this page
https://metraipolis.com/documento/dc_575defd22fc9

How to cite

Graphic Matroid Secretary without the Graph — arXiv:2608.11413 — arXiv (en), https://arxiv.org/abs/2608.11413 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_575defd22fc9 (Metraipolis archive dc_575defd22fc9, sha256 ae11ca81b54be7238310cac4b6950c3c1689d99fa4efc5ae1c1a455d7be3ea0d)
BibTeX
@misc{dc575defd22fc9,
  title = {Graphic Matroid Secretary without the Graph — arXiv:2608.11413},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.11413},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_575defd22fc9; sha256 ae11ca81b54be7238310cac4b6950c3c1689d99fa4efc5ae1c1a455d7be3ea0d},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.11413. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The matroid secretary problem (MSP) is one of the cleanest, and most captivating open problems in online algorithms. The famous MSP conjecture stipulates that there exists a constant-competitive algorithm, yet to date the best known algorithms are $O(\log \log (\text{rank}))$ competitive. It is widely believed that all information that an algorithm for the MSP should use is information that is available through an independence oracle on the already arrived elements. Despite this, there are natural classes of matroids where a constant-competitive algorithm is known if we are given additional upfront information about the matroid; while no such algorithm is known if all the algorithm can use is an independence oracle on the arrived elements. In this work, we tackle the perhaps most appealing such class of matroids, graphic matroids. We develop an algorithm for the MSP that has access to the independence oracle only. Our algorithm runs in polynomial time, and if the underlying matroid is graphic, it produces an independent set whose weight is at least $1/36$ of the maximum-weight independent set. Ours is the first constant-competitive algorithm for MSP on unknown graphic matroids.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-13 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.11413 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T05:48:37.114Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-13?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).