Online Stochastic Matching: New Algorithms with Better Bounds
We consider variants of the online stochastic bipartite matching problem motivated by Internet advertising display applications, as introduced in Feldman et al. [Feldman J, Mehta A, Mirrokni VS, Muthukrishnan S (2009) Online stochastic matching: Beating 1 − 1/e. FOCS '09: Proc. 50th Annual IEEE...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute for Operations Research and the Management Sciences (INFORMS)
2015
|
| Online Access: | http://hdl.handle.net/1721.1/100449 https://orcid.org/0000-0002-8585-6566 |
| _version_ | 1811097489612210176 |
|---|---|
| author | Jaillet, Patrick Lu, Xin |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Jaillet, Patrick Lu, Xin |
| author_sort | Jaillet, Patrick |
| collection | MIT |
| description | We consider variants of the online stochastic bipartite matching problem motivated by Internet advertising display applications, as introduced in Feldman et al. [Feldman J, Mehta A, Mirrokni VS, Muthukrishnan S (2009) Online stochastic matching: Beating 1 − 1/e. FOCS '09: Proc. 50th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Washington, DC), 117–126]. In this setting, advertisers express specific interests into requests for impressions of different types. Advertisers are fixed and known in advance, whereas requests for impressions come online. The task is to assign each request to an interested advertiser (or to discard it) immediately upon its arrival.
In the adversarial online model, the ranking algorithm of Karp et al. [Karp RM, Vazirani UV, Varirani VV (1990) An optimal algorithm for online bipartite matching. STOC '90: Proc. 22nd Annual ACM Sympos. Theory Comput. (ACM, New York), 352–358] provides a best possible randomized algorithm with competitive ratio 1 − 1/e ≈ 0.632.
In the stochastic i.i.d. model, when requests are drawn repeatedly and independently from a known probability distribution over the different impression types, Feldman et al. [Feldman J, Mehta A, Mirrokni VS, Muthukrishnan S (2009) Online stochastic matching: Beating 1 − 1/e. FOCS '09: Proc. 50th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Washington, DC), 117–126] prove that one can do better than 1 − 1/e. Under the restriction that the expected number of request of each impression type is an integer, they provide a 0.670-competitive algorithm, later improved by Bahmani and Kapralov [Bahmani B, Kapralov M (2010) Improved bounds for online stochastic matching. ESA '10: Proc. 22nd Annual Eur. Sympos. Algorithms (Springer-Verlag, Berlin, Heidelberg), 170–181] to 0.699 and by Manshadi et al. [Manshadi V, Gharan SO, Saberi A (2012) Online stochastic matching: Online actions based on offline statistics. Math. Oper. Res. 37(4):559–573] to 0.705. Without this integrality restriction, Manshadi et al. are able to provide a 0.702-competitive algorithm.
In this paper we consider a general class of online algorithms for the i.i.d. model that improve on all these bounds and that use computationally efficient offline procedures (based on the solution of simple linear programs of maximum flow types). Under the integrality restriction on the expected number of impression types, we get a 1 − 2e[superscript −2](≈0.729)-competitive algorithm. Without this restriction, we get a 0.706-competitive algorithm.
Our techniques can also be applied to other related problems such as the online stochastic vertex-weighted bipartite matching problem as defined in Aggarwal et al. [Aggarwal G, Goel G, Karande C, Mehta A (2011) Online vertex-weighted bipartite matching and single-bid budgeted allocations. SODA '11: Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1253–1264]. For this problem, we obtain a 0.725-competitive algorithm under the stochastic i.i.d. model with integral arrival rate.
Finally, we show the validity of all our results under a Poisson arrival model, removing the need to assume that the total number of arrivals is fixed and known in advance, as is required for the analysis of the stochastic i.i.d. models described above. |
| first_indexed | 2024-09-23T17:00:13Z |
| format | Article |
| id | mit-1721.1/100449 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T17:00:13Z |
| publishDate | 2015 |
| publisher | Institute for Operations Research and the Management Sciences (INFORMS) |
| record_format | dspace |
| spelling | mit-1721.1/1004492022-09-29T23:02:13Z Online Stochastic Matching: New Algorithms with Better Bounds Jaillet, Patrick Lu, Xin Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Massachusetts Institute of Technology. Operations Research Center Jaillet, Patrick Lu, Xin We consider variants of the online stochastic bipartite matching problem motivated by Internet advertising display applications, as introduced in Feldman et al. [Feldman J, Mehta A, Mirrokni VS, Muthukrishnan S (2009) Online stochastic matching: Beating 1 − 1/e. FOCS '09: Proc. 50th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Washington, DC), 117–126]. In this setting, advertisers express specific interests into requests for impressions of different types. Advertisers are fixed and known in advance, whereas requests for impressions come online. The task is to assign each request to an interested advertiser (or to discard it) immediately upon its arrival. In the adversarial online model, the ranking algorithm of Karp et al. [Karp RM, Vazirani UV, Varirani VV (1990) An optimal algorithm for online bipartite matching. STOC '90: Proc. 22nd Annual ACM Sympos. Theory Comput. (ACM, New York), 352–358] provides a best possible randomized algorithm with competitive ratio 1 − 1/e ≈ 0.632. In the stochastic i.i.d. model, when requests are drawn repeatedly and independently from a known probability distribution over the different impression types, Feldman et al. [Feldman J, Mehta A, Mirrokni VS, Muthukrishnan S (2009) Online stochastic matching: Beating 1 − 1/e. FOCS '09: Proc. 50th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Washington, DC), 117–126] prove that one can do better than 1 − 1/e. Under the restriction that the expected number of request of each impression type is an integer, they provide a 0.670-competitive algorithm, later improved by Bahmani and Kapralov [Bahmani B, Kapralov M (2010) Improved bounds for online stochastic matching. ESA '10: Proc. 22nd Annual Eur. Sympos. Algorithms (Springer-Verlag, Berlin, Heidelberg), 170–181] to 0.699 and by Manshadi et al. [Manshadi V, Gharan SO, Saberi A (2012) Online stochastic matching: Online actions based on offline statistics. Math. Oper. Res. 37(4):559–573] to 0.705. Without this integrality restriction, Manshadi et al. are able to provide a 0.702-competitive algorithm. In this paper we consider a general class of online algorithms for the i.i.d. model that improve on all these bounds and that use computationally efficient offline procedures (based on the solution of simple linear programs of maximum flow types). Under the integrality restriction on the expected number of impression types, we get a 1 − 2e[superscript −2](≈0.729)-competitive algorithm. Without this restriction, we get a 0.706-competitive algorithm. Our techniques can also be applied to other related problems such as the online stochastic vertex-weighted bipartite matching problem as defined in Aggarwal et al. [Aggarwal G, Goel G, Karande C, Mehta A (2011) Online vertex-weighted bipartite matching and single-bid budgeted allocations. SODA '11: Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1253–1264]. For this problem, we obtain a 0.725-competitive algorithm under the stochastic i.i.d. model with integral arrival rate. Finally, we show the validity of all our results under a Poisson arrival model, removing the need to assume that the total number of arrivals is fixed and known in advance, as is required for the analysis of the stochastic i.i.d. models described above. National Science Foundation (U.S.) (Grant 1029603) United States. Office of Naval Research (Grant N00014-09-1-0326) United States. Office of Naval Research (Grant N00014-12-1-0033) 2015-12-21T14:35:28Z 2015-12-21T14:35:28Z 2013-09 2012-05 Article http://purl.org/eprint/type/JournalArticle 0364-765X 1526-5471 http://hdl.handle.net/1721.1/100449 Jaillet, Patrick, and Xin Lu. “Online Stochastic Matching: New Algorithms with Better Bounds.” Mathematics of OR 39, no. 3 (August 2014): 624–646. https://orcid.org/0000-0002-8585-6566 en_US http://dx.doi.org/10.1287/moor.2013.0621 Mathematics of Operations Research Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute for Operations Research and the Management Sciences (INFORMS) MIT web domain |
| spellingShingle | Jaillet, Patrick Lu, Xin Online Stochastic Matching: New Algorithms with Better Bounds |
| title | Online Stochastic Matching: New Algorithms with Better Bounds |
| title_full | Online Stochastic Matching: New Algorithms with Better Bounds |
| title_fullStr | Online Stochastic Matching: New Algorithms with Better Bounds |
| title_full_unstemmed | Online Stochastic Matching: New Algorithms with Better Bounds |
| title_short | Online Stochastic Matching: New Algorithms with Better Bounds |
| title_sort | online stochastic matching new algorithms with better bounds |
| url | http://hdl.handle.net/1721.1/100449 https://orcid.org/0000-0002-8585-6566 |
| work_keys_str_mv | AT jailletpatrick onlinestochasticmatchingnewalgorithmswithbetterbounds AT luxin onlinestochasticmatchingnewalgorithmswithbetterbounds |