File Download
Links for fulltext
(May Require Subscription)
 Publisher Website: 10.1137/1.9781611973730.78
 Scopus: eid_2s2.084938236482
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Conference Paper: Revealing optimal thresholds for generalized secretary problem via continuous LP: impacts on online Kitem auction and bipartite Kmatching with random arrival order
Title  Revealing optimal thresholds for generalized secretary problem via continuous LP: impacts on online Kitem auction and bipartite Kmatching with random arrival order 

Authors  
Issue Date  2015 
Publisher  Society for Industrial and Applied Mathematics. 
Citation  The 26th Annual ACMSIAM Symposium on Discrete Algorithms (SODA 2015), San Diego, CA., 46 January 2015. In Conference Proceedings, 2015, p. 11691188 How to Cite? 
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/ethreshold 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 2item auction with random arriving bids (the ifuniform 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 1item 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 Kmatching with random arrival order that has at least the same performance guarantee. 
Persistent Identifier  http://hdl.handle.net/10722/214754 
ISBN 
DC Field  Value  Language 

dc.contributor.author  Chan, HTH   
dc.contributor.author  Chen, F   
dc.contributor.author  Jiang, S   
dc.date.accessioned  20150821T11:54:15Z   
dc.date.available  20150821T11:54:15Z   
dc.date.issued  2015   
dc.identifier.citation  The 26th Annual ACMSIAM Symposium on Discrete Algorithms (SODA 2015), San Diego, CA., 46 January 2015. In Conference Proceedings, 2015, p. 11691188   
dc.identifier.isbn  9781611973747   
dc.identifier.uri  http://hdl.handle.net/10722/214754   
dc.description.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/ethreshold 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 2item auction with random arriving bids (the ifuniform 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 1item 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 Kmatching with random arrival order that has at least the same performance guarantee.   
dc.language  eng   
dc.publisher  Society for Industrial and Applied Mathematics.   
dc.relation.ispartof  Proceedings of the TwentySixth Annual ACMSIAM Symposium on Discrete Algorithms   
dc.rights  © 2015 Society for Industrial and Applied Mathematics. First Published in Proceedings of the TwentySixth Annual ACMSIAM Symposium on Discrete Algorithms in 2015, published by the Society for Industrial and Applied Mathematics (SIAM).   
dc.title  Revealing optimal thresholds for generalized secretary problem via continuous LP: impacts on online Kitem auction and bipartite Kmatching with random arrival order   
dc.type  Conference_Paper   
dc.identifier.email  Chan, HTH: hubert@cs.hku.hk   
dc.identifier.email  Chen, F: feier@hku.hk   
dc.identifier.authority  Chan, HTH=rp01312   
dc.description.nature  postprint   
dc.identifier.doi  10.1137/1.9781611973730.78   
dc.identifier.scopus  eid_2s2.084938236482   
dc.identifier.hkuros  247365   
dc.identifier.spage  1169   
dc.identifier.epage  1188   
dc.publisher.place  United States   
dc.customcontrol.immutable  sml 150902   