Revealing optimal thresholds for generalized secretary problem via continuous LP: Impacts on Online K-Item auction and bipartite K-Matching with random arrival order

T. H.Hubert Chant, Fei Chen, Shaofeng H.C. Jiang

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

5 Citations (Scopus)

Abstract

We consider the general (J, K)-secretary problem, where n totally ordered items arrive in a random order. An algorithm observes the relative merits of arriving items and is allowed to make J selections. The objective is to maximize the expected number of items selected among the K best items. Buchbinder, Jain and Singh proposed a finite linear program (LP) that completely characterizes the problem, but it is difficult to analyze the asymptotic behavior of its optimal solution as n tends to infinity. Instead, we prove a formal connection between the finite model and an infinite model, where there are a countably infinite number of items, each of which has arrival time drawn independently and uniformly from [0, 1]. The finite LP extends to a continuous LP, whose complementary slackness conditions reveal an optimal algorithm which involves JK thresholds that play a similar role as the 1/e-threshold in the optimal classical secretary algorithm. In particular, for the case K=1, the J optimal thresholds have a nice "rational description". Our continuous LP analysis gives a very clear perspective on the problem, and the new insights inspire us; to solve two related problems. 1. We settle the open problem whether algorithms based only on relative merits can achieve optimal ratio for matroid secretary problems. We show that, for online 2-item auction with random arriving bids (the if-uniform matroid problem with K=2), an algorithm making decisions based only on relative merits cannot achieve the optimal ratio. This is in contrast with the folklore that, for online 1-item auction, no algorithm can have performance ratio strictly larger than 1/e, which is achievable by an algorithm that considers only relative merits. 2. We give a general transformation technique that takes any monotone algorithm (such as thresholdalgorithms) for the (K, K)-secretary problem, and constructs an algorithm for online bipartite K-matching with random arrival order that has at least the same performance guarantee.

Original languageEnglish
Title of host publicationProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Pages1169-1188
Number of pages20
Publication statusPublished - 2015
MoE publication typeA4 Article in a conference publication
EventACM-SIAM Symposium on Discrete Algorithms - San Diego, United States
Duration: 4 Jan 20156 Jan 2015
Conference number: 26

Conference

ConferenceACM-SIAM Symposium on Discrete Algorithms
Abbreviated titleSODA
CountryUnited States
CitySan Diego
Period04/01/201506/01/2015

Fingerprint Dive into the research topics of 'Revealing optimal thresholds for generalized secretary problem via continuous LP: Impacts on Online K-Item auction and bipartite K-Matching with random arrival order'. Together they form a unique fingerprint.

Cite this