{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T21:43:04Z","timestamp":1771623784026,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":44,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,6,19]],"date-time":"2017-06-19T00:00:00Z","timestamp":1497830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"DARPA SIMPLEX grant"},{"name":"NSF CAREER award","award":["CCF-1053605"],"award-info":[{"award-number":["CCF-1053605"]}]},{"name":"DARPA GRAPHS-AFOSR grant","award":["FA 9550-12-1-0423"],"award-info":[{"award-number":["FA 9550-12-1-0423"]}]},{"name":"Medium grant","award":["CCF-1161365"],"award-info":[{"award-number":["CCF-1161365"]}]},{"name":"NSF BIGDATA grant","award":["IIS-1546108"],"award-info":[{"award-number":["IIS-1546108"]}]},{"name":"NSF award","award":["CCF-1512964"],"award-info":[{"award-number":["CCF-1512964"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2017,6,19]]},"DOI":"10.1145\/3055399.3055479","type":"proceedings-article","created":{"date-parts":[[2017,6,15]],"date-time":"2017-06-15T20:27:45Z","timestamp":1497558465000},"page":"61-71","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":33,"title":["Beating 1-1\/e for ordered prophets"],"prefix":"10.1145","author":[{"given":"Melika","family":"Abolhassani","sequence":"first","affiliation":[{"name":"University of Maryland at College Park, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Soheil","family":"Ehsani","sequence":"additional","affiliation":[{"name":"University of Maryland at College Park, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hossein","family":"Esfandiari","sequence":"additional","affiliation":[{"name":"University of Maryland at College Park, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MohammadTaghi","family":"HajiAghayi","sequence":"additional","affiliation":[{"name":"University of Maryland at College Park, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Kleinberg","sequence":"additional","affiliation":[{"name":"Cornell University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Brendan","family":"Lucier","sequence":"additional","affiliation":[{"name":"Microsoft Research, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,6,19]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.90"},{"key":"e_1_3_2_2_2_1","unstructured":"Saeed Alaei MohammadTaghi Hajiaghayi and Vahid Liaghat. 2012.  Saeed Alaei MohammadTaghi Hajiaghayi and Vahid Liaghat. 2012."},{"key":"e_1_3_2_2_3_1","unstructured":"Online prophet-inequality matching with applications to ad allocation. In EC.  Online prophet-inequality matching with applications to ad allocation. In EC."},{"key":"e_1_3_2_2_4_1","volume-title":"Approx","author":"Alaei Saeed","unstructured":"Saeed Alaei , MohammadTaghi Hajiaghayi , and Vahid Liaghat . 2013. The online stochastic generalized assignment problem . In Approx . Springer . Saeed Alaei, MohammadTaghi Hajiaghayi, and Vahid Liaghat. 2013. The online stochastic generalized assignment problem. In Approx. Springer."},{"key":"e_1_3_2_2_5_1","volume-title":"Adcell: Ad allocation in cellular networks. In ESA.","author":"Alaei Saeed","year":"2011","unstructured":"Saeed Alaei , Mohammad T Hajiaghayi , Vahid Liaghat , Dan Pei , and Barna Saha . 2011 . Adcell: Ad allocation in cellular networks. In ESA. Saeed Alaei, Mohammad T Hajiaghayi, Vahid Liaghat, Dan Pei, and Barna Saha. 2011. Adcell: Ad allocation in cellular networks. In ESA."},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1283383.1283429"},{"key":"e_1_3_2_2_7_1","unstructured":"Niv Buchbinder Kamal Jain and Joseph Seffi Naor. 2007.  Niv Buchbinder Kamal Jain and Joseph Seffi Naor. 2007."},{"key":"e_1_3_2_2_8_1","unstructured":"Online primal-dual algorithms for maximizing ad-auctions revenue. In ESA. Springer 253\u2013264.   Online primal-dual algorithms for maximizing ad-auctions revenue. In ESA. Springer 253\u2013264."},{"key":"e_1_3_2_2_9_1","unstructured":"Shuchi Chawla Jason Hartline David Malec and Balasubramanian Sivan. 2010.  Shuchi Chawla Jason Hartline David Malec and Balasubramanian Sivan. 2010."},{"key":"e_1_3_2_2_10_1","unstructured":"Multi-parameter mechanism design and sequential posted pricing. (2010).  Multi-parameter mechanism design and sequential posted pricing. (2010)."},{"key":"e_1_3_2_2_11_1","volume-title":"Kleinberg","author":"Chawla Shuchi","year":"2007","unstructured":"Shuchi Chawla , Jason D. Hartline , and Robert D . Kleinberg . 2007 . Shuchi Chawla, Jason D. Hartline, and Robert D. Kleinberg. 2007."},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250946"},{"key":"e_1_3_2_2_13_1","unstructured":"Sina Dehghani Soheil Ehsani MohammadTaghi Hajiaghayi Vahid Liaghat and Saeed Seddighin. 2015. Online Survivable Network Design and Prophets. (2015).  Sina Dehghani Soheil Ehsani MohammadTaghi Hajiaghayi Vahid Liaghat and Saeed Seddighin. 2015. Online Survivable Network Design and Prophets. (2015)."},{"key":"e_1_3_2_2_14_1","unstructured":"Sina Dehghani Soheil Ehsani MohammadTaghi Hajiaghayi and Saeed Seddighin. 2016. Stochastic k-Server Problem. (2016).  Sina Dehghani Soheil Ehsani MohammadTaghi Hajiaghayi and Saeed Seddighin. 2016. Stochastic k-Server Problem. (2016)."},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1566374.1566384"},{"key":"e_1_3_2_2_16_1","volume-title":"Algorithms-ESA","author":"D\u00fctting Paul","year":"2015","unstructured":"Paul D\u00fctting and Robert Kleinberg . 2015. Polymatroid prophet inequalities . In Algorithms-ESA 2015 . Springer , 437\u2013449. Paul D\u00fctting and Robert Kleinberg. 2015. Polymatroid prophet inequalities. In Algorithms-ESA 2015. Springer, 437\u2013449."},{"key":"e_1_3_2_2_17_1","volume-title":"Algorithms-ESA","author":"Esfandiari Hossein","year":"2015","unstructured":"Hossein Esfandiari , MohammadTaghi Hajiaghayi , Vahid Liaghat , and Morteza Monemizadeh . 2015. Prophet Secretary . In Algorithms-ESA 2015 . Springer , 496\u2013 508. Hossein Esfandiari, MohammadTaghi Hajiaghayi, Vahid Liaghat, and Morteza Monemizadeh. 2015. Prophet Secretary. In Algorithms-ESA 2015. Springer, 496\u2013 508."},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764536"},{"key":"e_1_3_2_2_19_1","unstructured":"Uriel Feige and Jan Vondrak. 2006.  Uriel Feige and Jan Vondrak. 2006."},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.14"},{"key":"e_1_3_2_2_21_1","unstructured":"Jon Feldman Aranyak Mehta Vahab Mirrokni and S Muthukrishnan. 2009.  Jon Feldman Aranyak Mehta Vahab Mirrokni and S Muthukrishnan. 2009."},{"key":"e_1_3_2_2_22_1","volume-title":"Foundations of Computer Science, 2009. FOCS\u201909. 50th Annual IEEE Symposium on. IEEE, 117\u2013126","author":"Online","unstructured":"Online stochastic matching : Beating 1-1\/e . In Foundations of Computer Science, 2009. FOCS\u201909. 50th Annual IEEE Symposium on. IEEE, 117\u2013126 . Online stochastic matching: Beating 1-1\/e. In Foundations of Computer Science, 2009. FOCS\u201909. 50th Annual IEEE Symposium on. IEEE, 117\u2013126."},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722139"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1347082.1347185"},{"key":"e_1_3_2_2_25_1","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"G\u00f6bel Oliver","unstructured":"Oliver G\u00f6bel , Martin Hoefer , Thomas Kesselheim , Thomas Schleiden , and Berthold V\u00f6cking . 2014. Online independent set beyond the worst-case: Secretaries, prophets, and periods . In International Colloquium on Automata, Languages, and Programming . Springer , 508\u2013519. Oliver G\u00f6bel, Martin Hoefer, Thomas Kesselheim, Thomas Schleiden, and Berthold V\u00f6cking. 2014. Online independent set beyond the worst-case: Secretaries, prophets, and periods. In International Colloquium on Automata, Languages, and Programming. Springer, 508\u2013519."},{"key":"e_1_3_2_2_26_1","unstructured":"Mohammad T. Hajiaghayi Robert Kleinberg and Tuomas Sandholm. 2007. Automated online mechanism design and prophet inequalities. In AAAI. 58\u201365.   Mohammad T. Hajiaghayi Robert Kleinberg and Tuomas Sandholm. 2007. Automated online mechanism design and prophet inequalities. In AAAI. 58\u201365."},{"key":"e_1_3_2_2_27_1","volume-title":"Comparisons of stop rule and supremum expectations of iid random variables. The Annals of Probability","author":"Hill Theodore P","year":"1982","unstructured":"Theodore P Hill and Robert P Kertz . 1982. Comparisons of stop rule and supremum expectations of iid random variables. The Annals of Probability ( 1982 ), 336\u2013345. Theodore P Hill and Robert P Kertz. 1982. Comparisons of stop rule and supremum expectations of iid random variables. The Annals of Probability (1982), 336\u2013345."},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"crossref","unstructured":"DP Kennedy. 1985.  DP Kennedy. 1985.","DOI":"10.2307\/1444799"},{"key":"e_1_3_2_2_29_1","volume-title":"The Annals of Probability 13, 2","author":"Optimal","year":"1985","unstructured":"Optimal stopping of independent random variables and maximizing prophets. The Annals of Probability 13, 2 ( 1985 ), 566\u2013571. Optimal stopping of independent random variables and maximizing prophets. The Annals of Probability 13, 2 (1985), 566\u2013571."},{"key":"e_1_3_2_2_30_1","volume-title":"Prophet-type inequalities for multi-choice optimal stopping. Stochastic Processes and their Applications 24, 1","author":"Kennedy DP","year":"1987","unstructured":"DP Kennedy . 1987. Prophet-type inequalities for multi-choice optimal stopping. Stochastic Processes and their Applications 24, 1 ( 1987 ), 77\u201388. DP Kennedy. 1987. Prophet-type inequalities for multi-choice optimal stopping. Stochastic Processes and their Applications 24, 1 (1987), 77\u201388."},{"key":"e_1_3_2_2_31_1","unstructured":"Robert P Kertz. 1986.  Robert P Kertz. 1986."},{"key":"e_1_3_2_2_32_1","volume-title":"Advances in applied probability","author":"Comparison","year":"1986","unstructured":"Comparison of optimal value and constrained maxima expectations for independent random variables. Advances in applied probability ( 1986 ), 311\u2013340. Comparison of optimal value and constrained maxima expectations for independent random variables. Advances in applied probability (1986), 311\u2013340."},{"key":"e_1_3_2_2_33_1","unstructured":"Robert Kleinberg Bo Waggoner and E. Glen Weyl. 2016.  Robert Kleinberg Bo Waggoner and E. Glen Weyl. 2016."},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2940716.2940760"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213991"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"crossref","unstructured":"U. Krengel and L Sucheston. 1977. Semiamarts and finite values. In Bull. Am. Math. Soc.  U. Krengel and L Sucheston. 1977. Semiamarts and finite values. In Bull. Am. Math. Soc.","DOI":"10.1090\/S0002-9904-1977-14378-4"},{"key":"e_1_3_2_2_37_1","unstructured":"U. Krengel and L Sucheston. 1978. On semiamarts amarts and processes with finite value. In In Kuelbs J. ed. Probability on Banach Spaces.  U. Krengel and L Sucheston. 1978. On semiamarts amarts and processes with finite value. In In Kuelbs J. ed. Probability on Banach Spaces."},{"key":"e_1_3_2_2_38_1","unstructured":"Aranyak Mehta Amin Saberi Umesh Vazirani and Vijay Vazirani. 2007.  Aranyak Mehta Amin Saberi Umesh Vazirani and Vijay Vazirani. 2007."},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1284320.1284321"},{"key":"e_1_3_2_2_40_1","volume-title":"Shayan Oveis Gharan, and Morteza Zadimoghaddam","author":"Mirrokni Vahab S","year":"2012","unstructured":"Vahab S Mirrokni , Shayan Oveis Gharan, and Morteza Zadimoghaddam . 2012 . Vahab S Mirrokni, Shayan Oveis Gharan, and Morteza Zadimoghaddam. 2012."},{"key":"e_1_3_2_2_41_1","volume-title":"Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 1690\u20131701","author":"Simultaneous","unstructured":"Simultaneous approximations for adversarial and stochastic online budgeted allocation . In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 1690\u20131701 . Simultaneous approximations for adversarial and stochastic online budgeted allocation. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 1690\u20131701."},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793250767"},{"key":"e_1_3_2_2_43_1","volume-title":"Beyond matroids: Secretary Problem and Prophet Inequality with general constraints. arXiv preprint arXiv:1604.00357","author":"Rubinstein Aviad","year":"2016","unstructured":"Aviad Rubinstein . 2016. Beyond matroids: Secretary Problem and Prophet Inequality with general constraints. arXiv preprint arXiv:1604.00357 ( 2016 ). Aviad Rubinstein. 2016. Beyond matroids: Secretary Problem and Prophet Inequality with general constraints. arXiv preprint arXiv:1604.00357 (2016)."},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.2307\/1910412"}],"event":{"name":"STOC '17: Symposium on Theory of Computing","location":"Montreal Canada","acronym":"STOC '17","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055479","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055399.3055479","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:19Z","timestamp":1750217779000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055479"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,19]]},"references-count":44,"alternative-id":["10.1145\/3055399.3055479","10.1145\/3055399"],"URL":"https:\/\/doi.org\/10.1145\/3055399.3055479","relation":{},"subject":[],"published":{"date-parts":[[2017,6,19]]},"assertion":[{"value":"2017-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}