Formal Barriers to Simple Algorithms for the Matroid Secretary Problem

Maryam Bahrani, Hedyeh Beyhaghi, Sahil Singla, S. Matthew Weinberg

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Babaioff et al. [4] introduced the matroid secretary problem in 2007, a natural extension of the classic single-choice secretary problem to matroids, and conjectured that a constant-competitive online algorithm exists. The conjecture still remains open despite substantial partial progress, including constant-competitive algorithms for numerous special cases of matroids, and an O(log log rank ) -competitive algorithm in the general case. Many of these algorithms follow principled frameworks. The limits of these frameworks are previously unstudied, and prior work establishes only that a handful of particular algorithms cannot resolve the matroid secretary conjecture. We initiate the study of impossibility results for frameworks to resolve this conjecture. We establish impossibility results for a natural class of greedy algorithms and for randomized partition algorithms, both of which contain known algorithms that resolve special cases.

Original languageEnglish (US)
Title of host publicationWeb and Internet Economics - 17th International Conference, WINE 2021, Proceedings
EditorsMichal Feldman, Hu Fu, Inbal Talgam-Cohen
PublisherSpringer Science and Business Media Deutschland GmbH
Pages280-298
Number of pages19
ISBN (Print)9783030946753
DOIs
StatePublished - 2022
Event17th International Conference on Web and Internet Economics, WINE 2021 - Virtual, Online
Duration: Dec 14 2021Dec 17 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13112 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference17th International Conference on Web and Internet Economics, WINE 2021
CityVirtual, Online
Period12/14/2112/17/21

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Keywords

  • Graph theory
  • Greedy algorithms
  • Matroids
  • Optimal stopping theory
  • Secretary problem

Fingerprint

Dive into the research topics of 'Formal Barriers to Simple Algorithms for the Matroid Secretary Problem'. Together they form a unique fingerprint.

Cite this