Secretary Problems with Non-Uniform Arrival Order
From MaRDI portal
Abstract: For many online problems, it is known that the uniform arrival order enables the design of algorithms with much better performance guarantees than under worst-case. The quintessential example is the secretary problem. If the sequence of elements is presented in uniformly random order there is an algorithm that picks the maximum value with probability 1/e, whereas no non-trivial performance guarantee is possible if the elements arrive in worst-case order. This work initiates an investigation into relaxations of the random-ordering hypothesis in online algorithms, by focusing on the secretary problems. We present two sets of properties of distributions over permutations as sufficient conditions, called the block-independence property and uniform-induced-ordering property. We show these two are asymptotically equivalent by borrowing some techniques from the approximation theory. Moreover, we show they both imply the existence of secretary algorithms with constant probability of correct selection, approaching the optimal constant 1/e in the limit. We substantiate our idea by providing several constructions of distributions that satisfy block-independence. We also show that {Theta}(log log n) is the minimum entropy of any permutation distribution that permits constant probability of correct selection in the secretary problem with n elements. While our block-independence condition is sufficient for constant probability of correct selection, it is not necessary; however, we present complexity-theoretic evidence that no simple necessary and sufficient criterion exists. Finally, we explore the extent to which the performance guarantees of other algorithms are preserved when one relaxes the uniform random ordering assumption, obtaining a positive result for Kleinberg's multiple-choice secretary algorithm and a negative result for the weighted bipartite matching algorithm of Korula and Pal.
Recommendations
Cites work
- Approximate distance oracles
- Approximate distance oracles with constant query time
- Automata, Languages and Programming
- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Fast C-K-R partitions of sparse graphs
- Near-Linear Time Construction of Sparse Neighborhood Covers
- On approximate distance labels and routing schemes with affine stretch
- On sparse spanners of weighted graphs
- Ramsey partitions and proximity data structures
- Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
- Shortest-path queries in static networks
Cited in
(17)- Opportunity costs in the game of best choice
- Avoiding patterns and making the best choice
- Stable secretaries
- The secretary problem with biased arrival order via a Mallows distribution
- The secretary problem with distributions
- Strategy-indifferent games of best choice
- The returning secretary
- Primal beats dual on online packing LPs in the random-order model
- Strong algorithms for the ordinal matroid secretary problem
- Online resource allocation under partially predictable demand
- A Framework for the Secretary Problem on the Intersection of Matroids
- Secretary and online matching problems with machine learned advice
- The secretary problem with non-uniform arrivals via a left-to-right minimum exponentially tilted distribution
- Partially ordered secretaries
- Knapsack secretary with bursty adversary
- Robust algorithms under adversarial injections
- Competitive analysis with a sample and the secretary problem
This page was built for publication: Secretary Problems with Non-Uniform Arrival Order
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941585)
