On variants of the matroid secretary problem

DOI10.1007/978-3-642-23719-5_29zbMATH Open1307.68101arXiv1104.4081OpenAlexW2567949245MaRDI QIDQ2017872FDOQ2017872

Authors: Shayan Oveis Gharan, Jan Vondrák 

Publication date: 23 March 2015

Published in: Algorithmica, Algorithms – ESA 2011 (Search for Journal in Brave)

Abstract: We present a number of positive and negative results for variants of the matroid secretary problem. Most notably, we design a constant-factor competitive algorithm for the "random assignment" model where the weights are assigned randomly to the elements of a matroid, and then the elements arrive on-line in an adversarial order (extending a result of Soto cite{Soto11}). This is under the assumption that the matroid is known in advance. If the matroid is unknown in advance, we present an $O(logrlogn)$-approximation, and prove that a better than $O(logn/loglogn)$ approximation is impossible. This resolves an open question posed by Babaioff et al. cite{BIK07}. As a natural special case, we also consider the classical secretary problem where the number of candidates $n$ is unknown in advance. If $n$ is chosen by an adversary from $1,\mathrm{...},N$, we provide a nearly tight answer, by providing an algorithm that chooses the best candidate with probability at least $1/(H_{N-1}+1)$ and prove that a probability better than $1/H_N$ cannot be achieved (where $H_N$ is the $N$-th harmonic number).

Full work available at URL: https://arxiv.org/abs/1104.4081

Recommendations

• Matroid secretary problem in the random assignment model
• Matroid secretary problem in the random-assignment model
• Improved competitive ratio for the matroid secretary problem
• Matroid Secretary Problems

zbMATH Keywords

online optimizationmatroidssecretary problem

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Combinatorial probability (60C05) Combinatorial aspects of matroids and geometric lattices (05B35) Stopping times; optimal stopping problems; gambling theory (60G40)

Cites Work

• Title not available (Why is that?)
• A multiple-choice secretary algorithm with applications to online auctions
• Matroids, secretary problems, and online mechanisms
• Online stochastic packing applied to display ad allocation
• Submodular secretary problem and extensions
• Secretary problems: laminar matroid and interval scheduling
• Improved competitive ratio for the matroid secretary problem
• Title not available (Why is that?)
• Algorithms for Secretary Problems on Graphs and Hypergraphs
• Dynamic Programming and Decision Theory
• Who solved the secretary problem? With comments and a rejoinder by the author
• The Secretary Problem with an Unknown Number of Options
• Secretary Problems via Linear Programming
• The secretary problem with an unknown number of candidates
• Competitive Weighted Matching in Transversal Matroids
• Matroid secretary problem in the random assignment model

Cited In (1)

• Packing returning secretaries

This page was built for publication: On variants of the matroid secretary problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2017872)