Secretary problem: graphs, matroids and greedoids

DOI10.1007/S43069-021-00092-XMaRDI QIDQ2068844zbMATH OpenOpenAlexFDO

Authors Wojciech Kordecki

Publication date 20 January 2022

Published in SN Operations Research Forum (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

cloud computingdiscrete structureindenpendencesecretary problem

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Applications of graph theory (05C90) Stopping times; optimal stopping problems; gambling theory (60G40) Decision theory (91B06)

Abstract: In the paper the generalisation of the well known "secretary problem" is considered. The aim of the paper is to give a generalised model in such a way that the chosen set of the possible best $k$ elements have to be independent of all rejected elements. This condition is formulated using the theory of greedoids and in their special cases -- matroids and antimatroids. Examples of some special cases of greedoids (uniform, graphical matroids and binary trees) are considered.

Recommendations

• Matroids, secretary problems, and online mechanisms
• Matroid Secretary Problems
• The Secretary Problem with a Choice Function

Cites work

• A multiple-choice secretary algorithm with applications to online auctions
• Combinatorial optimization. Theory and algorithms.
• Greedoids
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 4137538 (Why is no real title available?)
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• scientific article; zbMATH DE number 3383344 (Why is no real title available?)
• Matroid secretary problem in the random-assignment model
• Matroid Secretary Problems
• Partial-order analogue of the secretary problem: The binary tree case
• Random graphs and complex networks. Volume 1
• Random graphs.
• Strong algorithms for the ordinal matroid secretary problem
• Structural properties of greedoids
• The secretary problem on an unknown poset
• Who solved the secretary problem

Cited in

(5)

• Matroid Secretary Problems
• Tree-cover ratio of graphs with asymptotic convergence identical to that of the secretary problem
• A Framework for the Secretary Problem on the Intersection of Matroids
• scientific article; zbMATH DE number 7650251 (Why is no real title available?)
• A note on the satisficing policy of the secretary problem

This page was built for publication: Secretary problem: graphs, matroids and greedoids

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