Secretary Problems via Linear Programming

79 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Online Adversarial Attacks (2021, background): “Most prominently, Buchbinder et al. [2014] and Chan et al. [2014] proved that the k-secretary problem can be solved optimally (in terms of competitive ratio) using linear programs (LPs), assuming a fixed length of n for the data stream.”
New Results for the $k$-Secretary Problem (2020, methodology): “ch could be a key insight into the general case. From a technical point of view, we analyze the algorithms using basic combinatorial constructs exclusively. This is in contrast to previous approaches [14, 22] which can only be analyzed using heavyweight linear programming techniques. The combinatori”
Secretaries with Advice (2020, methodology): “Our formulation generalize the linear program of Buchbinder, Jain, and Singh [7] to our more challenging setting.”
Competitive Analysis with a Sample and the Secretary Problem (2019, unknown): “Overall we get (cid:0) (cid:1) We note that Theorem 3.8 can also be derived from the work of Buchbinder et al. [4], by including the constraint that the ﬁrst h candidates must be rejected in the linear program that characterizes all algorithms for the secretary problem.”
Revealing Optimal Thresholds for Generalized Secretary Problem via Continuous LP: Impacts on Online K-Item Auction and Bipartite K-Matching with Random Arrival Order (2015, methodology): “Buchbinder, Jain and Singh [4] considered the following generalized secretary problem.”