Secretary Problems with Non-Uniform Arrival Order

DOI10.1145/2746539.2746602zbMath1321.68516arXiv1502.02155MaRDI QIDQ2941585

Thomas Kesselheim, Rad Niazadeh, Robert D. Kleinberg

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

online algorithms; average-case analysis; secretary problems

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W27: Online algorithms; streaming algorithms

Related Items

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, Opportunity costs in the game of best choice, Avoiding patterns and making the best choice, The secretary problem with biased arrival order via a Mallows distribution, Strategy-indifferent games of best choice

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming