{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T02:11:55Z","timestamp":1777342315372,"version":"3.51.4"},"publisher-location":"Cham","reference-count":38,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031598340","type":"print"},{"value":"9783031598357","type":"electronic"}],"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_22","type":"book-chapter","created":{"date-parts":[[2024,5,21]],"date-time":"2024-05-21T07:05:03Z","timestamp":1716275103000},"page":"294-308","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Online Combinatorial Assignment in\u00a0Independence Systems"],"prefix":"10.1007","author":[{"given":"Javier","family":"Marinkovic","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2219-8401","authenticated-orcid":false,"given":"Jos\u00e9 A.","family":"Soto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0817-7356","authenticated-orcid":false,"given":"Victor","family":"Verdugo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,5,22]]},"reference":[{"key":"22_CR1","doi-asserted-by":"crossref","unstructured":"Adamczyk, M., W\u0142odarczyk, M.: Random order contention resolution schemes. In: FOCS 2018, pp. 790\u2013801 (2018)","DOI":"10.1109\/FOCS.2018.00080"},{"key":"22_CR2","doi-asserted-by":"crossref","unstructured":"Assadi, S., Kesselheim, T., Singla, S.: Improved truthful mechanisms for subadditive combinatorial auctions: breaking the logarithmic barrier. In: SODA 2021, pp. 653\u2013661 (2021)","DOI":"10.1137\/1.9781611976465.40"},{"issue":"1","key":"22_CR3","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1145\/3440959.3440964","volume":"18","author":"S Assadi","year":"2020","unstructured":"Assadi, S., Singla, S.: Improved truthful mechanisms for combinatorial auctions with submodular bidders. ACM SIGecom Exch. 18(1), 19\u201327 (2020)","journal-title":"ACM SIGecom Exch."},{"key":"22_CR4","doi-asserted-by":"crossref","unstructured":"Babaioff, M., Immorlica, N., Kempe, D., Kleinberg, R.: Matroid secretary problems. J. ACM 65(6), 1\u201326 (2018)","DOI":"10.1145\/3212512"},{"key":"22_CR5","doi-asserted-by":"crossref","unstructured":"Babaioff, M., Lucier, B., Nisan, N., Paes Leme, R.: On the efficiency of the walrasian mechanism. In: EC 2014, pp. 783\u2013800 (2014)","DOI":"10.1145\/2600057.2602850"},{"key":"22_CR6","doi-asserted-by":"crossref","unstructured":"Baldwin, E., Klemperer, P.: Understanding preferences: demand types, and the existence of equilibrium with indivisibilities. Econometrica 87(3), 867\u2013932 (2019)","DOI":"10.3982\/ECTA13693"},{"key":"22_CR7","unstructured":"Brubach, B., Grammel, N., Ma, W., Srinivasan, A.: Improved guarantees for offline stochastic matching via new ordered contention resolution schemes. In: NeurIPS 2021, vol. 32, pp. 27184\u201327195 (2021)"},{"key":"22_CR8","doi-asserted-by":"crossref","unstructured":"Correa, J., Cristi, A.: A constant factor prophet inequality for online combinatorial auctions. In: STOC 2023, pp. 686\u2013697 (2023)","DOI":"10.1145\/3564246.3585151"},{"key":"22_CR9","doi-asserted-by":"crossref","unstructured":"Correa, J., Cristi, A., Fielbaum, A., Pollner, T., Weinberg, S.M.: Optimal item pricing in online combinatorial auctions. In: IPCO 2022, pp. 126\u2013139 (2022)","DOI":"10.1007\/978-3-031-06901-7_10"},{"key":"22_CR10","doi-asserted-by":"crossref","unstructured":"Dobzinski, S.: Breaking the logarithmic barrier for truthful combinatorial auctions with submodular bidders. In: STOC 2016, pp. 940\u2013948 (2016)","DOI":"10.1145\/2897518.2897569"},{"key":"22_CR11","doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Nisan, N., Schapira, M.: Approximation algorithms for combinatorial auctions with complement-free bidders. In: STOC 2005, pp. 610\u2013618 (2005)","DOI":"10.1145\/1060590.1060681"},{"issue":"3","key":"22_CR12","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1137\/20M1323850","volume":"49","author":"P D\u00fctting","year":"2020","unstructured":"D\u00fctting, P., Feldman, M., Kesselheim, T., Lucier, B.: Prophet inequalities made easy: stochastic optimization by pricing nonstochastic inputs. SIAM J. Comput. 49(3), 540\u2013582 (2020)","journal-title":"SIAM J. Comput."},{"key":"22_CR13","first-page":"627","volume":"4","author":"EB Dynkin","year":"1963","unstructured":"Dynkin, E.B.: The optimum choice of the instant for stopping a Markov process. Soviet Math. Dokl 4, 627\u2013629 (1963)","journal-title":"Soviet Math. Dokl"},{"key":"22_CR14","doi-asserted-by":"crossref","unstructured":"Edmonds, J.: Matroid intersection. Ann. Discret. Math. 4, 39\u201349. Elsevier (1979)","DOI":"10.1016\/S0167-5060(08)70817-3"},{"key":"22_CR15","doi-asserted-by":"crossref","unstructured":"Ehsani, S., Hajiaghayi, M.T., Kesselheim, T., Singla, S.: Prophet secretary for combinatorial auctions and matroids. In: SODA 2018, pp. 700\u2013714 (2018)","DOI":"10.1137\/1.9781611975031.46"},{"key":"22_CR16","doi-asserted-by":"crossref","unstructured":"Ezra, T., Feldman, M., Gravin, N., Tang, Z.G.: Online stochastic max-weight matching: prophet inequality for vertex and edge arrival models. In: EC 2020, pp. 769\u2013787 (2020)","DOI":"10.1145\/3391403.3399513"},{"key":"22_CR17","doi-asserted-by":"crossref","unstructured":"Ezra, T., Feldman, M., Gravin, N., Tang, Z.G.: General graphs are easier than bipartite graphs: tight bounds for secretary matching. In: EC 2022, pp. 1148\u20131177 (2022)","DOI":"10.1145\/3490486.3538290"},{"key":"22_CR18","doi-asserted-by":"crossref","unstructured":"Feldman, M., Gravin, N., Lucier, B.: Combinatorial walrasian equilibrium. In: STOC 2013, pp. 61\u201370 (2013)","DOI":"10.1145\/2488608.2488617"},{"key":"22_CR19","doi-asserted-by":"crossref","unstructured":"Feldman, M., Svensson, O., Zenklusen, R.: A simple O(loglog(rank))-competitive algorithm for the matroid secretary problem. Math. Oper. Res. 43(2), 638\u2013650 (2018)","DOI":"10.1287\/moor.2017.0876"},{"key":"22_CR20","doi-asserted-by":"crossref","unstructured":"Feldman, M., Svensson, O., Zenklusen, R.: Online contention resolution schemes with applications to bayesian selection problems. SIAM J. Comput. 50(2), 255\u2013300 (2021)","DOI":"10.1137\/18M1226130"},{"key":"22_CR21","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1080\/01621459.1966.10502008","volume":"61","author":"JP Gilbert","year":"1966","unstructured":"Gilbert, J.P., Mosteller, F.: Recognizing the maximum of a sequence. J. Am. Stat. Assoc. 61, 35\u201376 (1966)","journal-title":"J. Am. Stat. Assoc."},{"key":"22_CR22","doi-asserted-by":"crossref","unstructured":"Hill, T.P., Kertz, R.P.: Comparisons of stop rule and supremum expectations of i.i.d. random variables. Ann. Probab. 10, 336\u2013345 (1982)","DOI":"10.1214\/aop\/1176993861"},{"key":"22_CR23","unstructured":"Jenkyns, T.A.: Matchoids: a generalization of matchings and matroids. PhD thesis, University of Waterloo (1975)"},{"key":"22_CR24","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Junger, M., et al. (eds.) 50 Years of Integer Programming 1958\u20132008. Springer, Berlin, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-540-68279-0_8","DOI":"10.1007\/978-3-540-68279-0_8"},{"key":"22_CR25","doi-asserted-by":"crossref","unstructured":"Kertz, R.P.: Stop rule and supremum expectations of i.i.d. random variables: a complete comparison by conjugate duality. J. Multivar. Anal. 19, 88\u2013112 (1986)","DOI":"10.1016\/0047-259X(86)90095-3"},{"key":"22_CR26","doi-asserted-by":"crossref","unstructured":"Kesselheim, T., Radke, K., T\u00f6nnis, A., V\u00f6cking, B.: An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. In: ESA 2013, pp. 589\u2013600 (2013)","DOI":"10.1007\/978-3-642-40450-4_50"},{"key":"22_CR27","doi-asserted-by":"crossref","unstructured":"Kleinberg, R., Weinberg, S.M.: Matroid prophet inequalities and applications to multi-dimensional mechanism design. Games Econ. Behav. 113, 97\u2013115 (2019)","DOI":"10.1016\/j.geb.2014.11.002"},{"key":"22_CR28","doi-asserted-by":"publisher","unstructured":"Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms. Springer, Berlin, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-24488-9","DOI":"10.1007\/978-3-642-24488-9"},{"key":"22_CR29","doi-asserted-by":"crossref","unstructured":"Korula, N., P\u00e1l, M.: Algorithms for secretary problems on graphs and hypergraphs. In: ICALP 2009, pp. 508\u2013520 (2009)","DOI":"10.1007\/978-3-642-02930-1_42"},{"key":"22_CR30","doi-asserted-by":"crossref","unstructured":"Lawler, E.L.: Matroid intersection algorithms. Math. Program. 9(1), 31\u201356 (1975)","DOI":"10.1007\/BF01681329"},{"issue":"2","key":"22_CR31","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/0095-8956(80)90066-0","volume":"28","author":"L Lov\u00e1sz","year":"1980","unstructured":"Lov\u00e1sz, L.: Matroid matching and some applications. J. Comb. Theory Ser. B 28(2), 208\u2013236 (1980)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"22_CR32","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1145\/3144722.3144725","volume":"16","author":"B Lucier","year":"2017","unstructured":"Lucier, B.: An economic view of prophet inequalities. ACM SIGecom Exch. 16(1), 24\u201347 (2017)","journal-title":"ACM SIGecom Exch."},{"key":"22_CR33","doi-asserted-by":"crossref","unstructured":"MacRury, C., Ma, W., Grammel, N.: On (random-order) online contention resolution schemes for the matching polytope of (bipartite) graphs. In: SODA 2023, pp. 1995\u20132014 (2023)","DOI":"10.1137\/1.9781611977554.ch76"},{"issue":"1\u20132","key":"22_CR34","first-page":"343","volume":"179","author":"Renato Paes Leme and Sam Chiu-wai Wong","year":"2020","unstructured":"Renato Paes Leme and Sam Chiu-wai Wong: Computing walrasian equilibria: fast algorithms and structural properties. Math. Program. 179(1\u20132), 343\u2013384 (2020)","journal-title":"Math. Program."},{"key":"22_CR35","doi-asserted-by":"crossref","unstructured":"Pollner, T., Roghani, M., Saberi, A., Wajc, D.: Improved online contention resolution for matchings and applications to the gig economy. In: EC 2022, pp. 321\u2013322 (2022)","DOI":"10.1145\/3490486.3538295"},{"key":"22_CR36","doi-asserted-by":"crossref","unstructured":"Rubinstein, A.: Beyond matroids: secretary problem and prophet inequality with general constraints. In: STOC 2016, pp. 324\u2013332, July 2016","DOI":"10.1145\/2897518.2897540"},{"issue":"4","key":"22_CR37","first-page":"1213","volume":"12","author":"E Samuel-Cahn","year":"1983","unstructured":"Samuel-Cahn, E.: Comparisons of threshold stop rule and maximum for independent nonnegative random variables. Ann. Probab. 12(4), 1213\u20131216 (1983)","journal-title":"Ann. Probab."},{"key":"22_CR38","doi-asserted-by":"crossref","unstructured":"Soto, J.A., Turkieltaub, A., Verdugo, V.: Strong algorithms for the ordinal matroid secretary problem. Math. Oper. Res. 46(2), 642\u2013673 (2021)","DOI":"10.1287\/moor.2020.1083"}],"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_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,21]],"date-time":"2024-05-21T07:13:59Z","timestamp":1716275639000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-59835-7_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031598340","9783031598357"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-59835-7_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"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":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"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"}}]}}