cs.DSNov 10, 2026

Multiple-Choice Secretary Problem with Predictions

Authors: Jing Yuan, Qi Cai, Xin Gao, Shaojie Tang

Organizations: University of North Texas · University at Buffalo

Abstract

We study the multiple-choice secretary problem, in which candidates arrive in uniformly random order and the goal is to select at most kk candidates to maximize their total value. We consider a setting where predictions of individual candidate values are available before any candidate arrives. Fujii and Yoshida's Learned Kleinberg algorithm achieves competitive loss O(min⁡{log⁡k/k,\eps})O(\min\{\log k/\sqrt{k},\eps\}), where kk is the selection capacity and \eps\eps is the maximum multiplicative prediction error. We remove the logarithmic factor through a sharper analysis of the same switching algorithm with a retuned threshold. The resulting competitive ratio is at least max⁡{0,1−min⁡{32/k,4\eps}}\max\{0,1-\min\{32/\sqrt{k},4\eps\}\}. In particular, exact predictions (\eps=0\eps=0) achieve the offline optimum on every arrival order.

Figures & tables

Explore similar work

May 21, 2026

The Secretary Problem with a Stochastic Precursor

In learning-augmented online algorithms, predictions are usually valued for what they say: a value estimate, a solution, or an algorithmic recommendation. This paper shows that predictions can also be valuable solely due to their arrival time. We study the fundamental secretary problem augmented with a stochastic precursor: a content-free signal that is guaranteed to arrive no later than the best item, but is otherwise stochastically timed. The signal does not carry any additional information; nevertheless, its timing alone changes the structure of optimal stopping. We characterize optimal policies in the random-order and adversarial-order models. In random order, a single uniformly timed precursor already gives success probability at least 12\frac12, improving on the classic 1e\frac1e benchmark. With increasingly late precursors, the success probability approaches 11. In adversarial order, for which traditional models do not admit strong guarantees, sufficiently concentrated precursors recover constant success guarantees. Our results show that such novel forms of asynchronous temporal information are a distinct and powerful form of advice in online decision making and may also be effective for other problems.
Oct 10, 2026

Certify the Decision, Not Every Score: Exact Top-k Selection from Few Evaluations

Choosing a few robust algorithms or schedules can require evaluating every candidate under many adverse scenarios, even though an agent only needs to identify the winners. A predictor may suggest those winners, but cannot rule out a surprise in an unevaluated scenario. We introduce Certified Adaptive Selection (CAS), which returns the exact top-kk set as soon as remaining uncertainty cannot change it. CAS keeps guaranteed lower and upper bounds on Expected Shortfall (ES), the average loss in the worst scenarios. Its stopping test compares the worst admissible selected candidate with the best admissible excluded one; for information-disjoint Cartesian intervals this one-cut test is necessary and sufficient. Prediction has a separate role: selecting the next outcome to evaluate, never authorizing the decision. For empirical ES with exact unit-cost queries, we compute in polynomial time the fewest evaluations that could have proved the realized decision in hindsight. Our prediction-guided agent CAS-PG is exact for every predictor, including adversarial ones. On two public algorithm-selection matrices, CAS-PG certifies the exact top three after 630 of 3150 and 981 of 2200 replayed queries, or 1.141.14 and 1.181.18 times that hindsight minimum. Without historical outcomes, its transcript-only variant requires 1.281.28 and 1.371.37 times the minimum, outperforming the tested non-predictive certified policies. Separately, a prediction-free CAS policy avoids 93.0%93.0\% of exact recourse solves in synthetic energy scheduling. One certificate thus supports several acquisition policies and separately proved risk/cost extensions: prediction changes the work, not the justified choice.
Jun 17, 2026

Learning Augmented Exact Exponential Algorithms

The field of learning-augmented algorithms has demonstrated that machine-learned predictions can bypass worst-case lower bounds across a wide range of problems. So far, however, the focus has been almost exclusively on polynomial-time algorithms, where predictions improve competitive ratios, approximation guarantees, or running times. In this paper, we raise the question of whether predictions can push the frontier of exact exponential-time algorithms for NP-hard problems. We answer this question affirmatively by proposing a general approach that augments an entire family of state-of-the-art exact algorithms for a variety of subset selection problems. We show that a noisy predictor that is only marginally better than random guessing suffices to provably reduce the search space, and that the resulting runtime speedup scales smoothly with the prediction quality. Importantly, our algorithms require only pairwise independence of predictions or, alternatively, do not require the knowledge of the predictor's accuracy - both strictly weaker and more realistic settings than typically assumed.