English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Suppose we are given integer $k \leq n$ and $n$ boxes labeled $1,\ldots, n$by an adversary, each containing a number chosen from an unknown distribution.We have to choose an order to sequentially open these boxes, and each time weopen the next box in this order, we learn its number. If we reject a number ina box, the box cannot be recalled. Our goal is to accept the $k$ largest ofthese numbers, without necessarily opening all boxes. This is the free ordermultiple-choice secretary problem. Free order variants were studied extensivelyfor the secretary and prophet problems. Kesselheim, Kleinberg, and Niazadeh KKN(STOC'15) initiated a study of randomness-efficient algorithms (with thecheapest order in terms of used random bits) for the free order secretaryproblems.  We present an algorithm for free order multiple-choice secretary, which issimultaneously optimal for the competitive ratio and used amount of randomness.I.e., we construct a distribution on orders with optimal entropy$\Theta(\log\log n)$ such that a deterministic multiple-threshold algorithm is$1-O(\sqrt{\log k/k})$-competitive. This improves in three ways the previousbest construction by KKN, whose competitive ratio is $1 - O(1/k^{1/3}) - o(1)$.Our competitive ratio is (near)optimal for the multiple-choice secretaryproblem; it works for exponentially larger parameter $k$; and our algorithm isa simple deterministic multiple-threshold algorithm, while that in KKN israndomized. We also prove a corresponding lower bound on the entropy of optimalsolutions for the multiple-choice secretary problem, matching entropy of ouralgorithm, where no such previous lower bound was known.  We obtain our algorithmic results with a host of new techniques, and withthese techniques we also improve significantly the previous results of KKNabout constructing entropy-optimal distributions for the classic free ordersecretary.

Optimal Algorithms for Free Order Multiple-Choice Secretary