{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,11]],"date-time":"2025-07-11T10:27:53Z","timestamp":1752229673694,"version":"3.40.3"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031598340"},{"type":"electronic","value":"9783031598357"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-59835-7_15","type":"book-chapter","created":{"date-parts":[[2024,5,21]],"date-time":"2024-05-21T07:05:03Z","timestamp":1716275103000},"page":"196-209","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Pairwise-Independent Contention Resolution"],"prefix":"10.1007","author":[{"given":"Anupam","family":"Gupta","sequence":"first","affiliation":[]},{"given":"Jinqiao","family":"Hu","sequence":"additional","affiliation":[]},{"given":"Gregory","family":"Kehne","sequence":"additional","affiliation":[]},{"given":"Roie","family":"Levin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,5,22]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"Adamczyk, M., Wlodarczyk, M.: Random order contention resolution schemes. In: 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, 7\u20139 October 2018, pp. 790\u2013801. IEEE Computer Society (2018)","DOI":"10.1109\/FOCS.2018.00080"},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"Arsenis, M., Drosis, O., Kleinberg, R.: Constrained-order prophet inequalities. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, 10\u201313 January 2021, pp. 2034\u20132046. SIAM (2021)","DOI":"10.1137\/1.9781611976465.121"},{"key":"15_CR3","unstructured":"Azar, P.D., Kleinberg, R., Weinberg, S.M.: Prophet inequalities with limited information. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, 5\u20137 January 2014, pp. 1358\u20131377. SIAM (2014)"},{"key":"15_CR4","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1016\/j.geb.2018.05.006","volume":"118","author":"PD Azar","year":"2019","unstructured":"Azar, P.D., Kleinberg, R., Weinberg, S.M.: Prior independent mechanisms via prophet inequalities with limited information. Games Econ. Behav. 118, 511\u2013532 (2019)","journal-title":"Games Econ. Behav."},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"Babaioff, M., Dinitz, M., Gupta, A., Immorlica, N., Talwar, K.: Secretary problems: weights and discounts. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, 4\u20136 January 2009, pp. 1245\u20131254. SIAM (2009)","DOI":"10.1137\/1.9781611973068.135"},{"key":"15_CR6","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/978-3-662-48350-3_9","volume-title":"Algorithms - ESA 2015","author":"M Bateni","year":"2015","unstructured":"Bateni, M., Dehghani, S., Hajiaghayi, M., Seddighin, S.: Revenue maximization for selling multiple correlated items. In: Bansal, N., Finocchi, I. (eds.) Algorithms - ESA 2015. LNCS, vol. 9294, pp. 95\u2013105. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48350-3_9"},{"key":"15_CR7","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/978-3-030-94676-0_8","volume-title":"Web and Internet Economics","author":"I Caragiannis","year":"2021","unstructured":"Caragiannis, I., Gravin, N., Lu, P., Wang, Z.: Relaxing the independence assumption in sequential posted pricing, prophet inequality, and random bipartite matching. In: Feldman, M., Fu, H., Talgam-Cohen, I. (eds.) WINE 2021. LNCS, vol. 13112, pp. 131\u2013148. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-94676-0_8"},{"key":"15_CR8","unstructured":"Caramanis, C., Faw, M., Papadigenopoulos, O., Pountourakis, E.: Single-sample prophet inequalities revisited. CoRR abs\/2103.13089 (2021)"},{"key":"15_CR9","unstructured":"Chawla, S., Gergatsouli, E., McMahan, J., Tzamos, C.: Approximating Pandora\u2019s box with correlations. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2023. LIPIcs, Atlanta, Georgia, USA, 11\u201313 September 2023, vol. 275, pp. 26:1\u201326:24. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023)"},{"issue":"6","key":"15_CR10","doi-asserted-by":"publisher","first-page":"1831","DOI":"10.1137\/110839655","volume":"43","author":"C Chekuri","year":"2014","unstructured":"Chekuri, C., Vondr\u00e1k, J., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM J. Comput. 43(6), 1831\u20131879 (2014)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"15_CR11","doi-asserted-by":"publisher","first-page":"1452","DOI":"10.1287\/moor.2020.1105","volume":"46","author":"JR Correa","year":"2021","unstructured":"Correa, J.R., Foncea, P., Hoeksma, R., Oosterwijk, T., Vredeveld, T.: Posted price mechanisms and optimal threshold strategies for random arrivals. Math. Oper. Res. 46(4), 1452\u20131478 (2021)","journal-title":"Math. Oper. Res."},{"issue":"5","key":"15_CR12","doi-asserted-by":"publisher","first-page":"1807","DOI":"10.1137\/13094030X","volume":"43","author":"M Dinitz","year":"2014","unstructured":"Dinitz, M., Kortsarz, G.: Matroid secretary for regular and decomposable matroids. SIAM J. Comput. 43(5), 1807\u20131830 (2014)","journal-title":"SIAM J. Comput."},{"key":"15_CR13","unstructured":"Dughmi, S.: Matroid secretary is equivalent to contention resolution. In: 13th Innovations in Theoretical Computer Science Conference, ITCS 2022. LIPIcs, Berkeley, CA, USA, 31 January\u20133 February 2022, vol. 215, pp. 58:1\u201358:23. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022)"},{"key":"15_CR14","unstructured":"Dughmi, S., Kalayci, Y.H., Patel, N.: Limitations of stochastic selection problems with pairwise independent priors. CoRR abs\/2310.05240 (2023)"},{"issue":"3","key":"15_CR15","doi-asserted-by":"publisher","first-page":"1685","DOI":"10.1137\/15M1029394","volume":"31","author":"H Esfandiari","year":"2017","unstructured":"Esfandiari, H., Hajiaghayi, M., Liaghat, V., Monemizadeh, M.: Prophet secretary. SIAM J. Discrete Math. 31(3), 1685\u20131701 (2017)","journal-title":"SIAM J. Discrete Math."},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"Feldman, M., Svensson, O., Zenklusen, R.: Online contention resolution schemes. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1014\u20131033. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch72"},{"key":"15_CR17","unstructured":"Giambartolomei, G., Mallmann-Trenn, F., Saona, R.: Prophet inequalities: separating random order from order selection. CoRR abs\/2304.04024 (2023)"},{"key":"15_CR18","unstructured":"Goyal, V., Humair, S., Papadigenopoulos, O., Zeevi, A.: MNL-Prophet: sequential assortment selection under uncertainty. CoRR abs\/2308.05207 (2023)"},{"key":"15_CR19","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kehne, G., Levin, R.: Set covering with our eyes wide shut. In: Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 4530\u20134553. SIAM (2024)","DOI":"10.1137\/1.9781611977912.160"},{"key":"15_CR20","doi-asserted-by":"crossref","unstructured":"Hill, T.P., Kertz, R.P.: A survey of prophet inequalities in optimal stopping theory. In: Strategies for Sequential Search and Selection in real time, Amherst, MA (1990). Contemp. Math. 125, 191\u2013207. American Mathematical Society, Providence (1992)","DOI":"10.1090\/conm\/125\/1160620"},{"key":"15_CR21","doi-asserted-by":"crossref","unstructured":"Immorlica, N., Singla, S., Waggoner, B.: Prophet inequalities with linear correlations and augmentations. In: EC 2020: The 21st ACM Conference on Economics and Computation, Virtual Event, Hungary, 13\u201317 July 2020, pp. 159\u2013185. ACM (2020)","DOI":"10.1145\/3391403.3399452"},{"key":"15_CR22","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.geb.2014.11.002","volume":"113","author":"R Kleinberg","year":"2019","unstructured":"Kleinberg, R., Weinberg, S.M.: Matroid prophet inequalities and applications to multi-dimensional mechanism design. Games Econom. Behav. 113, 97\u2013115 (2019)","journal-title":"Games Econom. Behav."},{"key":"15_CR23","unstructured":"Krengel, U., Sucheston, L.: On semiamarts, amarts, and processes with finite value. In: Probability on Banach Spaces. Advanced Probability Related Topics, vol.\u00a04, pp. 197\u2013266. Dekker, New York (1978)"},{"key":"15_CR24","unstructured":"Lee, E., Singla, S.: Optimal online contention resolution schemes via ex-ante prophet inequalities. In: 26th Annual European Symposium on Algorithms, ESA 2018. LIPIcs, Helsinki, Finland, 20\u201322 August 2018, vol.\u00a0112, pp. 57:1\u201357:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"issue":"4","key":"15_CR25","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1561\/0400000009","volume":"1","author":"M Luby","year":"2005","unstructured":"Luby, M., Wigderson, A.: Pairwise independence and derandomization. Found. Trends Theor. Comput. Sci. 1(4), 237\u2013301 (2005)","journal-title":"Found. Trends Theor. Comput. Sci."},{"issue":"4","key":"15_CR26","doi-asserted-by":"publisher","first-page":"1482","DOI":"10.1214\/aos\/1176350605","volume":"15","author":"Y Rinott","year":"1987","unstructured":"Rinott, Y., Samuel-Cahn, E.: Comparisons of optimal stopping values and prophet inequalities for negatively dependent random variables. Ann. Statist. 15(4), 1482\u20131490 (1987)","journal-title":"Ann. Statist."},{"key":"15_CR27","doi-asserted-by":"crossref","unstructured":"Rinott, Y., Samuel-Cahn, E.: Optimal stopping values and prophet inequalities for some dependent random variables. In: Stochastic Inequalities, Seattle, WA (1991). IMS Lecture Notes Monograph Series, vol.\u00a022, pp. 343\u2013358. Institute of Mathematical Statistics, Hayward (1992)","DOI":"10.1214\/lnms\/1215461961"},{"key":"15_CR28","unstructured":"Rubinstein, A.: Beyond matroids: secretary problem and prophet inequality with general constraints. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, 18\u201321 June 2016, pp. 324\u2013332. ACM (2016)"},{"key":"15_CR29","doi-asserted-by":"crossref","unstructured":"Rubinstein, A., Singla, S.: Combinatorial prophet inequalities. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, 16\u201319 January 2017, pp. 1671\u20131687. SIAM (2017)","DOI":"10.1137\/1.9781611974782.110"},{"key":"15_CR30","unstructured":"Rubinstein, A., Wang, J.Z., Weinberg, S.M.: Optimal single-choice prophet inequalities from samples. In: 11th Innovations in Theoretical Computer Science Conference, ITCS 2020. LIPIcs, Seattle, Washington, USA, 12\u201314 January 2020, vol.\u00a0151, pp. 60:1\u201360:10. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"key":"15_CR31","series-title":"Algorithms and Combinatorics","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics, vol. 24. Springer, Berlin (2003)"},{"key":"15_CR32","unstructured":"Seymour, P.: Decomposition of regular matroids. A source book in matroid theory, p. 339 (1986)"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-59835-7_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,21]],"date-time":"2024-05-21T07:13:21Z","timestamp":1716275601000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-59835-7_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031598340","9783031598357"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-59835-7_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"22 May 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Wroc\u0142aw","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 July 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 July 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ipco2024.ii.uni.wroc.pl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}