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

• On variants of the matroid secretary problem
• 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 (24)

• Strong algorithms for the ordinal matroid secretary problem
• A Framework for the Secretary Problem on the Intersection of Matroids
• The best-or-worst and the postdoc problems with random number of candidates
• Matroid prophet inequalities and applications to multi-dimensional mechanism design
• Matroid secretary problem in the random assignment model
• Advances on matroid secretary problems: free order model and laminar case
• The simulated greedy algorithm for several submodular matroid secretary problems
• Optimal composition ordering problems for piecewise linear functions
• A simple \(O(\log\log(\mathrm{rank}))\)-competitive algorithm for the matroid secretary problem
• Matroid Secretary Problems
• Title not available (Why is that?)
• Formal barriers to simple algorithms for the matroid secretary problem
• The returning secretary
• Improved competitive ratios for submodular secretary problems (extended abstract)
• Prior independent mechanisms via prophet inequalities with limited information
• Matroids, secretary problems, and online mechanisms
• Constant-competitiveness for random assignment matroid secretary without knowing the matroid
• Secretary problems: laminar matroid and interval scheduling
• On variants of the matroid secretary problem
• Secretary problem: graphs, matroids and greedoids
• Generalized sequential stochastic assignment problem
• Online \((J, K)\)-search problem and its competitive analysis
• Online k-max Search Algorithms with Applications to the Secretary Problem
• Matroid secretary problem in the random-assignment model

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)