File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Revealing optimal thresholds for generalized secretary problem via continuous LP: impacts on online K-item auction and bipartite K-matching with random arrival order

TitleRevealing optimal thresholds for generalized secretary problem via continuous LP: impacts on online K-item auction and bipartite K-matching with random arrival order
Authors
Issue Date2015
PublisherSociety for Industrial and Applied Mathematics.
Citation
The 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), San Diego, CA., 4-6 January 2015. In Conference Proceedings, 2015, p. 1169-1188 How to Cite?
AbstractWe 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.
Persistent Identifierhttp://hdl.handle.net/10722/214754
ISBN

 

DC FieldValueLanguage
dc.contributor.authorChan, HTH-
dc.contributor.authorChen, F-
dc.contributor.authorJiang, S-
dc.date.accessioned2015-08-21T11:54:15Z-
dc.date.available2015-08-21T11:54:15Z-
dc.date.issued2015-
dc.identifier.citationThe 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), San Diego, CA., 4-6 January 2015. In Conference Proceedings, 2015, p. 1169-1188-
dc.identifier.isbn978-1-61197-374-7-
dc.identifier.urihttp://hdl.handle.net/10722/214754-
dc.description.abstractWe 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.-
dc.languageeng-
dc.publisherSociety for Industrial and Applied Mathematics.-
dc.relation.ispartofProceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms-
dc.rightsProceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms. Copyright © Society for Industrial and Applied Mathematics.-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.titleRevealing optimal thresholds for generalized secretary problem via continuous LP: impacts on online K-item auction and bipartite K-matching with random arrival order-
dc.typeConference_Paper-
dc.identifier.emailChan, HTH: hubert@cs.hku.hk-
dc.identifier.emailChen, F: feier@hku.hk-
dc.identifier.authorityChan, HTH=rp01312-
dc.description.naturepostprint-
dc.identifier.doi10.1137/1.9781611973730.78-
dc.identifier.scopuseid_2-s2.0-84938236482-
dc.identifier.hkuros247365-
dc.identifier.spage1169-
dc.identifier.epage1188-
dc.publisher.placeUnited States-
dc.customcontrol.immutablesml 150902-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats