## 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 language | English |
---|---|

Title of host publication | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |

Pages | 1169-1188 |

Number of pages | 20 |

Publication status | Published - 2015 |

MoE publication type | A4 Article in a conference publication |

Event | ACM-SIAM Symposium on Discrete Algorithms - San Diego, United States Duration: 4 Jan 2015 → 6 Jan 2015 Conference number: 26 |

### Conference

Conference | ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Abbreviated title | SODA |

Country | United States |

City | San Diego |

Period | 04/01/2015 → 06/01/2015 |