pith. sign in

arxiv: 2502.09834 · v2 · submitted 2025-02-14 · 💻 cs.DS

Optimal k-Secretary with Logarithmic Memory

Mingda Qiao , Wei Zhang This is my paper

Pith reviewed 2026-05-23 03:31 UTC · model grok-4.3

classification 💻 cs.DS
keywords k-secretary problemonline algorithmsmemory-bounded algorithmsquantile estimationcompetitive analysisrandom-order streamssublinear memory
0
0 comments X

The pith

A k-secretary algorithm matches the optimal competitive ratio using O(log k) words of memory.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies algorithms for the k-secretary problem that must select the k best items from a random-order stream while using limited memory. Prior optimal solutions required linear memory in k, but the authors show that O(log k) memory suffices by first proving a general reduction from k-secretary to the problem of estimating the k-th largest element in a stream. They then construct a quantile estimator that achieves the needed accuracy with O(log k) memory. A reader would care because many online selection tasks face similar memory constraints and the reduction cleanly separates the selection logic from the estimation subroutine.

Core claim

We establish a general reduction from k-secretary to random-order quantile estimation. Any quantile estimation algorithm with O(k^α) expected rank error yields a (1 - O(1/k^{1-α}))-competitive k-secretary algorithm with O(1) extra words of memory. We then give a quantile estimation algorithm that achieves O(√k) expected error using O(log k) memory, which produces a k-secretary algorithm matching the optimal 1 - O(1/√k) competitive ratio.

What carries the argument

The reduction from k-secretary to quantile estimation together with a new O(log k)-memory quantile estimator that returns an element whose rank error is O(√k) in expectation.

If this is right

  • The optimal competitive ratio for k-secretary is achievable without storing a linear number of items.
  • Quantile estimation in random order admits an O(log k)-memory solution with O(√k) expected error.
  • An alternative O(√k)-memory algorithm finds the exact k-th largest element with high probability.
  • The same reduction technique applies to other secretary variants once a suitable quantile estimator is available.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar reductions may allow memory-efficient solutions for related online selection problems such as matroid secretary or prophet inequalities.
  • The exact high-probability quantile algorithm could be useful as a building block for streaming data structures beyond secretary problems.
  • Practical implementations could test whether the O(log k) memory bound remains stable when arrival order deviates modestly from uniform randomness.

Load-bearing premise

A quantile estimation algorithm whose expected rank error is O(k^α) for some α<1 produces a k-secretary algorithm whose competitive ratio is 1 minus O(1/k^{1-α}).

What would settle it

A proof that every O(log k)-memory quantile estimator must incur Ω(k^{1/2+ε}) expected rank error for some ε>0 would falsify the claimed competitive ratio.

read the original abstract

We study memory-bounded algorithms for the $k$-secretary problem. The algorithm of Kleinberg (SODA 2005) achieves an optimal competitive ratio of $1 - O(1/\sqrt{k})$, yet a straightforward implementation requires $\Omega(k)$ memory. Our main result is a $k$-secretary algorithm that matches the optimal competitive ratio using $O(\log k)$ words of memory. We prove this result by establishing a general reduction from $k$-secretary to (random-order) quantile estimation, the problem of finding the $k$-th largest element in a stream. We show that a quantile estimation algorithm with an $O(k^{\alpha})$ expected error (in terms of the rank) gives a $(1 - O(1/k^{1-\alpha}))$-competitive $k$-secretary algorithm with $O(1)$ extra words. We then introduce a new quantile estimation algorithm that achieves an $O(\sqrt{k})$ expected error bound using $O(\log k)$ memory. Of independent interest, we give a different algorithm that uses $O(\sqrt{k})$ words and finds the $k$-th largest element exactly with high probability, generalizing a result of Munro and Paterson (1980).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper claims a k-secretary algorithm achieving the optimal competitive ratio 1-O(1/√k) using O(log k) words of memory. It establishes a general reduction showing that any quantile estimator with O(k^α) expected rank error yields a (1-O(1/k^{1-α}))-competitive k-secretary algorithm with O(1) extra words, then constructs an O(√k)-error quantile estimator using O(log k) memory. It also gives an O(√k)-memory algorithm that finds the exact k-th largest element w.h.p., generalizing Munro-Paterson.

Significance. If the reduction holds, the result is significant: it shows that the optimal Kleinberg ratio is achievable with logarithmic rather than linear memory. The general reduction from k-secretary to quantile estimation and the new O(√k)-error O(log k)-memory estimator are of independent interest; the exact w.h.p. algorithm is a clean generalization of prior work.

major comments (1)
  1. [Abstract] Abstract (general reduction paragraph): the claim that O(k^α) expected rank error in quantile estimation implies a (1-O(1/k^{1-α}))-competitive ratio. The analysis must explicitly bound how this expectation propagates through the online threshold-setting decisions; if the reduction only uses the expectation without concentration or additional arguments controlling threshold sensitivity, the competitive-ratio guarantee may fail to hold even when the quantile subroutine is correct.
minor comments (1)
  1. Clarify the precise memory model (word size, comparison model) used for the O(log k) and O(√k) bounds.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and for identifying this important point about the reduction. We address the comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract (general reduction paragraph): the claim that O(k^α) expected rank error in quantile estimation implies a (1-O(1/k^{1-α}))-competitive ratio. The analysis must explicitly bound how this expectation propagates through the online threshold-setting decisions; if the reduction only uses the expectation without concentration or additional arguments controlling threshold sensitivity, the competitive-ratio guarantee may fail to hold even when the quantile subroutine is correct.

    Authors: We thank the referee for this observation. The reduction (detailed in Section 3 of the manuscript) propagates the expected rank error via linearity of expectation applied to the indicator variables for selecting each element; because the competitive ratio itself is defined in expectation over the random order, no concentration is required. The sensitivity of each threshold decision to a rank deviation of size Δ is bounded by O(Δ/k) in the worst case, which directly yields the claimed O(1/k^{1-α}) loss when the expected error is O(k^α). We agree, however, that the current write-up leaves some of these bounding steps implicit. In the revision we will insert an explicit lemma (new Lemma 3.3) that isolates the propagation argument and states the sensitivity bound formally. revision: yes

Circularity Check

0 steps flagged

No significant circularity; reduction and estimator are independent contributions

full rationale

The paper presents a general reduction (abstract and §3) converting any quantile estimator with O(k^α) expected rank error into a (1-O(1/k^{1-α}))-competitive k-secretary algorithm using O(1) extra words. This reduction is stated as a standalone theorem independent of the specific estimator. A separate O(√k)-error, O(log k)-memory quantile estimator is then constructed and substituted to recover the Kleinberg ratio. No equation or claim reduces by construction to its own inputs, no fitted parameter is relabeled as a prediction, and no load-bearing step relies on a self-citation chain. The derivation is self-contained against the stated external benchmark (Kleinberg 2005) and does not exhibit any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on the standard random-order arrival model for secretary problems and basic facts from competitive analysis; no free parameters or new entities are introduced.

axioms (1)
  • domain assumption Candidates arrive in uniformly random order.
    Standard modeling assumption for the k-secretary problem invoked throughout the abstract.

pith-pipeline@v0.9.0 · 5743 in / 928 out tokens · 22676 ms · 2026-05-23T03:31:37.571704+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

47 extracted references · 47 canonical work pages · 1 internal anchor

  1. [1]

    Karlin, Nathan Klein, and Shayan Oveis Gharan

    Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. Matroid partition property and the secretary problem. In Innovations in Theoretical Computer Science (ITCS) , pages 2:1--2:9, 2023

    work page 2023

  2. [2]

    New results for the k-secretary problem

    Susanne Albers and Leon Ladewig. New results for the k-secretary problem. Theoretical Computer Science , 863:102--119, 2021

    work page 2021

  3. [3]

    Improved algorithms and analysis for secretary problems and generalizations

    Miklos Ajtai, Nimrod Megiddo, and Orli Waarts. Improved algorithms and analysis for secretary problems and generalizations. SIAM Journal on Discrete Mathematics , 14(1):1--27, 2001

    work page 2001

  4. [4]

    Submodular secretary problem with shortlists

    Shipra Agrawal, Mohammad Shadravan, and Cliff Stein. Submodular secretary problem with shortlists. In Innovations in Theoretical Computer Science (ITCS) , pages 1:1--1:19, 2019

    work page 2019

  5. [5]

    The secretary problem with interview cost

    R Bartoszy \'n ski and Z Govindarajulu. The secretary problem with interview cost. Sankhy \=a : The Indian Journal of Statistics, Series B , pages 11--28, 1978

    work page 1978

  6. [6]

    The secretary problem with reservation costs

    Elisabet Burjons, Matthias Gehnen, Henri Lotze, Daniel Mock, and Peter Rossmanith. The secretary problem with reservation costs. In International Computing and Combinatorics Conference , pages 553--564, 2021

    work page 2021

  7. [7]

    Matroids, secretary problems, and online mechanisms

    Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. Matroids, secretary problems, and online mechanisms. In Symposium on Discrete Algorithms (SODA) , pages 434--443, 2007

    work page 2007

  8. [8]

    A knapsack secretary problem with applications

    Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. A knapsack secretary problem with applications. In International Workshop on Approximation Algorithms for Combinatorial Optimization , pages 16--28, 2007

    work page 2007

  9. [9]

    Matroid secretary problems

    Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. Matroid secretary problems. Journal of the ACM (JACM) , 65(6):1--26, 2018

    work page 2018

  10. [10]

    Gradient descent is pareto-optimal in the oracle complexity and memory tradeoff for feasibility problems

    Moise Blanchard. Gradient descent is pareto-optimal in the oracle complexity and memory tradeoff for feasibility problems. In Foundations of Computer Science (FOCS) , pages 2413--2435, 2024

    work page 2024

  11. [11]

    Concentration inequalities for sampling without replacement

    R \'e mi Bardenet and Odalric-Ambrym Maillard. Concentration inequalities for sampling without replacement. Bernoulli , 21(3):1361--1385, 2015

    work page 2015

  12. [12]

    Memory-constrained algorithms for convex optimization via recursive cutting-planes

    Moise Blanchard, Junhui Zhang, and Patrick Jaillet. Memory-constrained algorithms for convex optimization via recursive cutting-planes. In Advances in Neural Information Processing Systems (NeurIPS) , pages 6156--6189, 2023

    work page 2023

  13. [13]

    Improved competitive ratio for the matroid secretary problem

    Sourav Chakraborty and Oded Lachish. Improved competitive ratio for the matroid secretary problem. In Symposium on Discrete Algorithms (SODA) , pages 1702--1712, 2012

    work page 2012

  14. [14]

    Optimal selection based on relative rank (the ``secretary problem'')

    Yuan-Shih Chow, Sigaiti Moriguti, Herbert Robbins, and Stephen Mitchell Samuels. Optimal selection based on relative rank (the ``secretary problem''). Israel Journal of mathematics , 2(2):81--90, 1964

    work page 1964

  15. [15]

    Matroid secretary for regular and decomposable matroids

    Michael Dinitz and Guy Kortsarz. Matroid secretary for regular and decomposable matroids. SIAM Journal on Computing , 43(5):1807--1830, 2014

    work page 2014

  16. [16]

    The optimum choice of the instant for stopping a markov process

    Evgenii Borisovich Dynkin. The optimum choice of the instant for stopping a markov process. Soviet Mathematics , 4:627--629, 1963

    work page 1963

  17. [17]

    Ferguson

    Thomas S. Ferguson. Who solved the secretary problem? Statistical science , 4(3):282--289, 1989

    work page 1989

  18. [18]

    P.R. Freeman. The secretary problem and its extensions: A review. International Statistical Review , pages 189--206, 1983

    work page 1983

  19. [19]

    A simple o (log log (rank))-competitive algorithm for the matroid secretary problem

    Moran Feldman, Ola Svensson, and Rico Zenklusen. A simple o (log log (rank))-competitive algorithm for the matroid secretary problem. In Symposium on Discrete Algorithms (SODA) , pages 1189--1201, 2014

    work page 2014

  20. [20]

    Combinatorial pen testing (or consumer surplus of deferred-acceptance auctions)

    Aadityan Ganesh and Jason Hartline. Combinatorial pen testing (or consumer surplus of deferred-acceptance auctions). arXiv preprint arXiv:2301.12462 , 2023

    work page arXiv 2023

  21. [21]

    Gilbert and Frederick Mosteller

    John P. Gilbert and Frederick Mosteller. Recognizing the maximum of a sequence. Journal of the American Statistical Association , 61(313):35--73, 1966

    work page 1966

  22. [22]

    Stream order and order statistics: Quantile estimation in random-order streams

    Sudipto Guha and Andrew McGregor. Stream order and order statistics: Quantile estimation in random-order streams. SIAM Journal on Computing , 38(5):2044--2059, 2009

    work page 2044

  23. [23]

    Extractor-based time-space lower bounds for learning

    Sumegha Garg, Ran Raz, and Avishay Tal. Extractor-based time-space lower bounds for learning. In Symposium on Theory of Computing (STOC) , pages 990--1002, 2018

    work page 2018

  24. [24]

    Optimal quantile estimation: beyond the comparison model

    Meghal Gupta, Mihir Singhal, and Hongxun Wu. Optimal quantile estimation: beyond the comparison model. In Foundations of Computer Science (FOCS) , pages 1137--1158, 2024

    work page 2024

  25. [25]

    The matroid secretary problem for minor-closed classes and random matroids

    Tony Huynh and Peter Nelson. The matroid secretary problem for minor-closed classes and random matroids. SIAM Journal on Discrete Mathematics , 34(1):163--176, 2020

    work page 2020

  26. [26]

    Advances on matroid secretary problems: Free order model and laminar case

    Patrick Jaillet, Jos \'e A Soto, and Rico Zenklusen. Advances on matroid secretary problems: Free order model and laminar case. In International Conference on Integer Programming and Combinatorial Optimization , pages 254--265, 2013

    work page 2013

  27. [27]

    Kleinberg

    Robert D. Kleinberg. A multiple-choice secretary algorithm with applications to online auctions. In Symposium on Discrete Algorithms (SODA) , pages 630--631, 2005

    work page 2005

  28. [28]

    Optimal quantile approximation in streams

    Zohar Karnin, Kevin Lang, and Edo Liberty. Optimal quantile approximation in streams. In Foundations of Computer Science (FOCS) , pages 71--78, 2016

    work page 2016

  29. [29]

    Time-space hardness of learning sparse parities

    Gillat Kol, Ran Raz, and Avishay Tal. Time-space hardness of learning sparse parities. In Symposium on Theory of Computing (STOC) , pages 1067--1080, 2017

    work page 2017

  30. [30]

    O (log log rank) competitive ratio for the matroid secretary problem

    Oded Lachish. O (log log rank) competitive ratio for the matroid secretary problem. In Foundations of Computer Science (FOCS) , pages 326--335, 2014

    work page 2014

  31. [31]

    D.V. Lindley. Dynamic programming and decision theory. Journal of the Royal Statistical Society: Series C (Applied Statistics) , 10(1):39--51, 1961

    work page 1961

  32. [32]

    Munro and M.S

    J.I. Munro and M.S. Paterson. Selection and sorting with limited storage. Theoretical Computer Science , 12(3):315--323, 1980

    work page 1980

  33. [33]

    Approximate medians and other quantiles in one pass and with limited memory

    Gurmeet Singh Manku, Sridhar Rajagopalan, and Bruce G Lindsay. Approximate medians and other quantiles in one pass and with limited memory. ACM SIGMOD Record , 27(2):426--435, 1998

    work page 1998

  34. [34]

    Rim, and Homin K

    Charles Masson, Jee E. Rim, and Homin K. Lee. Ddsketch: a fast and fully-mergeable quantile sketch with relative-error guarantees. Proceedings of the VLDB Endowment , 12(12):2195--2205, 2019

    work page 2019

  35. [35]

    Efficient convex optimization requires superlinear memory

    Annie Marsden, Vatsal Sharan, Aaron Sidford, and Gregory Valiant. Efficient convex optimization requires superlinear memory. In Conference on Learning Theory (COLT) , pages 2390--2430, 2022

    work page 2022

  36. [36]

    The shifting sands algorithm

    Andrew McGregor and Paul Valiant. The shifting sands algorithm. In Symposium on Discrete Algorithms (SODA) , pages 453--458, 2012

    work page 2012

  37. [37]

    A message forward scheduling based on a secretary problem for mobile relay nodes

    Ryo Nakano, Kazuya Tsukamoto, Masato Tsuru, and Yuji Oie. A message forward scheduling based on a secretary problem for mobile relay nodes. IEICE Technical Report , 110(448):357--362, 2011

    work page 2011

  38. [38]

    Near optimal memory-regret tradeoff for online learning

    Binghui Peng and Aviad Rubinstein. Near optimal memory-regret tradeoff for online learning. In Foundations of Computer Science (FOCS) , pages 1171--1194, 2023

    work page 2023

  39. [39]

    Online prediction in sub-linear space

    Binghui Peng and Fred Zhang. Online prediction in sub-linear space. In Symposium on Discrete Algorithms (SODA) , pages 1611--1634, 2023

    work page 2023

  40. [40]

    Online pen testing

    Mingda Qiao and Gregory Valiant. Online pen testing. In Innovations in Theoretical Computer Science (ITCS) , pages 91:1--91:26, 2023

    work page 2023

  41. [41]

    Fast learning requires good memory: A time-space lower bound for parity learning

    Ran Raz. Fast learning requires good memory: A time-space lower bound for parity learning. Journal of the ACM (JACM) , 66(1):1--18, 2018

    work page 2018

  42. [42]

    Matroid secretary problem in the random-assignment model

    Jos \'e A Soto. Matroid secretary problem in the random-assignment model. SIAM Journal on Computing , 42(1):178--211, 2013

    work page 2013

  43. [43]

    Memory-sample tradeoffs for linear regression with small error

    Vatsal Sharan, Aaron Sidford, and Gregory Valiant. Memory-sample tradeoffs for linear regression with small error. In Symposium on Theory of Computing (STOC) , pages 890--901, 2019

    work page 2019

  44. [44]

    Strong algorithms for the ordinal matroid secretary problem

    Jos \'e A Soto, Abner Turkieltaub, and Victor Verdugo. Strong algorithms for the ordinal matroid secretary problem. Mathematics of Operations Research , 46(2):642--673, 2021

    work page 2021

  45. [45]

    Memory, communication, and statistical queries

    Jacob Steinhardt, Gregory Valiant, and Stefan Wager. Memory, communication, and statistical queries. In Conference on Learning Theory (COLT) , pages 1490--1516, 2016

    work page 2016

  46. [46]

    Woodruff, Ziyu Xu, and Samson Zhou

    Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, and Samson Zhou. Memory bounds for the experts problem. In Symposium on Theory of Computing (STOC) , pages 1158--1171, 2022

    work page 2022

  47. [47]

    Information Theoretically Secure Databases

    Gregory Valiant and Paul Valiant. Information theoretically secure databases. arXiv preprint arXiv:1605.02646 , 2016

    work page internal anchor Pith review Pith/arXiv arXiv 2016