File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1137/1.9781611973730.78
- Scopus: eid_2-s2.0-84938236482
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
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
Title | Revealing 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 Date | 2015 |
Publisher | Society 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? |
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. |
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 | 2015-08-21T11:54:15Z | - |
dc.date.available | 2015-08-21T11:54:15Z | - |
dc.date.issued | 2015 | - |
dc.identifier.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 | - |
dc.identifier.isbn | 978-1-61197-374-7 | - |
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/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.language | eng | - |
dc.publisher | Society for Industrial and Applied Mathematics. | - |
dc.relation.ispartof | Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | - |
dc.rights | © 2015 Society for Industrial and Applied Mathematics. First Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM 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 K-item auction and bipartite K-matching 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_2-s2.0-84938236482 | - |
dc.identifier.hkuros | 247365 | - |
dc.identifier.spage | 1169 | - |
dc.identifier.epage | 1188 | - |
dc.publisher.place | United States | - |
dc.customcontrol.immutable | sml 150902 | - |