{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T07:54:51Z","timestamp":1777362891738,"version":"3.51.4"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2025,3,13]],"date-time":"2025-03-13T00:00:00Z","timestamp":1741824000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,3,13]],"date-time":"2025-03-13T00:00:00Z","timestamp":1741824000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100020884","name":"ANID","doi-asserted-by":"crossref","award":["CMM FB210005"],"award-info":[{"award-number":["CMM FB210005"]}],"id":[{"id":"10.13039\/501100020884","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100020884","name":"ANID","doi-asserted-by":"crossref","award":["FONDECYT 1231669"],"award-info":[{"award-number":["FONDECYT 1231669"]}],"id":[{"id":"10.13039\/501100020884","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100020884","name":"ANID","doi-asserted-by":"crossref","award":["FONDECYT 1241846"],"award-info":[{"award-number":["FONDECYT 1241846"]}],"id":[{"id":"10.13039\/501100020884","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100020884","name":"ANID","doi-asserted-by":"crossref","award":["Anillo ACT210005"],"award-info":[{"award-number":["Anillo ACT210005"]}],"id":[{"id":"10.13039\/501100020884","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2026,3]]},"DOI":"10.1007\/s10107-025-02213-4","type":"journal-article","created":{"date-parts":[[2025,3,13]],"date-time":"2025-03-13T07:41:08Z","timestamp":1741851668000},"page":"49-86","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Online combinatorial assignment in independence systems"],"prefix":"10.1007","volume":"216","author":[{"given":"Javier","family":"Marinkovic","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"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":[[2025,3,13]]},"reference":[{"key":"2213_CR1","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":"2213_CR2","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1214\/aop\/1176993861","volume":"10","author":"TP Hill","year":"1982","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)","journal-title":"Ann. Probab."},{"key":"2213_CR3","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."},{"issue":"4","key":"2213_CR4","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":"2213_CR5","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/0047-259X(86)90095-3","volume":"19","author":"RP Kertz","year":"1986","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)","journal-title":"J. Multivar. Anal."},{"issue":"1","key":"2213_CR6","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":"2213_CR7","doi-asserted-by":"crossref","unstructured":"Ehsani, S., Hajiaghayi, M., Kesselheim, T., Singla, S.: Prophet secretary for combinatorial auctions and matroids. In: SODA 2018, pp. 700\u2013714 (2018)","DOI":"10.1137\/1.9781611975031.46"},{"issue":"2","key":"2213_CR8","doi-asserted-by":"publisher","first-page":"642","DOI":"10.1287\/moor.2020.1083","volume":"46","author":"JA Soto","year":"2021","unstructured":"Soto, J.A., Turkieltaub, A., Verdugo, V.: Strong algorithms for the ordinal matroid secretary problem. Math. Oper. Res. 46(2), 642\u2013673 (2021)","journal-title":"Math. Oper. Res."},{"key":"2213_CR9","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":"2213_CR10","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":"2213_CR11","doi-asserted-by":"crossref","unstructured":"Rubinstein, A.: Beyond matroids: secretary problem and prophet inequality with general constraints. In: STOC 2016, pp. 324\u2013332 (2016)","DOI":"10.1145\/2897518.2897540"},{"issue":"1","key":"2213_CR12","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":"2213_CR13","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"},{"key":"2213_CR14","doi-asserted-by":"crossref","unstructured":"Babaioff, M., Lucier, B., Nisan, N., Paes\u00a0Leme, R.: On the efficiency of the walrasian mechanism. In: EC 2014, pp. 783\u2013800 (2014)","DOI":"10.1145\/2600057.2602850"},{"issue":"3","key":"2213_CR15","doi-asserted-by":"publisher","first-page":"867","DOI":"10.3982\/ECTA13693","volume":"87","author":"E Baldwin","year":"2019","unstructured":"Baldwin, E., Klemperer, P.: Understanding preferences:\u201cdemand types\u2019\u2019, and the existence of equilibrium with indivisibilities. Econometrica 87(3), 867\u2013932 (2019)","journal-title":"Econometrica"},{"key":"2213_CR16","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"},{"key":"2213_CR17","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":"2213_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":"2213_CR19","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"},{"issue":"1\u20132","key":"2213_CR20","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/s10107-018-1334-9","volume":"179","author":"R Paes Leme","year":"2020","unstructured":"Paes Leme, R., Wong, S.C.-w: Computing walrasian equilibria: fast algorithms and structural properties. Math. Program. 179(1\u20132), 343\u2013384 (2020)","journal-title":"Math. Program."},{"key":"2213_CR21","unstructured":"Ma, W., MacRury, C., Zhang, J.: Online contention resolution schemes for network revenue management and combinatorial auctions. arXiv:2403.05378 (2024)"},{"key":"2213_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68279-0_8","volume-title":"Reducibility Among Combinatorial Problems","author":"RM Karp","year":"2010","unstructured":"Karp, R.M.: Reducibility Among Combinatorial Problems. Springer, Berlin, Heidelberg (2010)"},{"key":"2213_CR23","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":"2213_CR24","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"},{"issue":"3","key":"2213_CR25","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1137\/20M1323850","volume":"49","author":"P Dutting","year":"2020","unstructured":"Dutting, 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":"2213_CR26","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":"2213_CR27","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"},{"issue":"2","key":"2213_CR28","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1287\/moor.2017.0876","volume":"43","author":"M Feldman","year":"2018","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)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"2213_CR29","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1137\/18M1226130","volume":"50","author":"M Feldman","year":"2021","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)","journal-title":"SIAM J. Comput."},{"key":"2213_CR30","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":"2213_CR31","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. EC 2022, 321\u2013322 (2022)","DOI":"10.1145\/3490486.3538295"},{"key":"2213_CR32","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"},{"key":"2213_CR33","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":"2213_CR34","doi-asserted-by":"crossref","unstructured":"Edmonds, J.: Matroid intersection. In: Annals of discrete mathematics vol. 4, pp. 39\u201349. Elsevier, Amsterdam, Netherlands (1979)","DOI":"10.1016\/S0167-5060(08)70817-3"},{"issue":"1","key":"2213_CR35","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/BF01681329","volume":"9","author":"EL Lawler","year":"1975","unstructured":"Lawler, E.L.: Matroid intersection algorithms. Math. Program. 9(1), 31\u201356 (1975)","journal-title":"Math. Program."},{"key":"2213_CR36","unstructured":"Bernhard, K., Vygen, J.: Combinatorial optimization: theory and algorithms. Springer, Third Edition, 2005. (2008)"},{"issue":"6","key":"2213_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3212512","volume":"65","author":"M Babaioff","year":"2018","unstructured":"Babaioff, M., Immorlica, N., Kempe, D., Kleinberg, R.: Matroid secretary problems. J. ACM 65(6), 1\u201326 (2018)","journal-title":"J. ACM"},{"issue":"2","key":"2213_CR38","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"},{"key":"2213_CR39","unstructured":"Jenkyns, T.: Matchoids: a generalization of matchings and matroids. Phd thesis, University of Waterloo (1975)"},{"issue":"2","key":"2213_CR40","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0095-8956(84)90023-6","volume":"36","author":"WH Cunningham","year":"1984","unstructured":"Cunningham, W.H.: Testing membership in matroid polyhedra. J. Combin. Theory Ser. B 36(2), 161\u2013188 (1984)","journal-title":"J. Combin. Theory Ser. B"},{"key":"2213_CR41","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"2012","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, vol. 2. Springer, Berlin, Heidelberg (2012)"},{"key":"2213_CR42","doi-asserted-by":"crossref","unstructured":"Correa, J., Foncea, P., Hoeksma, R., Oosterwijk, T., Vredeveld, T.: Posted price mechanisms for a random stream of customers. EC 2017, 169\u2013186 (2017)","DOI":"10.1145\/3033274.3085137"},{"issue":"113","key":"2213_CR43","first-page":"1","volume":"23","author":"J Correa","year":"2022","unstructured":"Correa, J., Cristi, A., Epstein, B., Soto, J.: The two-sided game of googol. J. Mach. Learn. Res. 23(113), 1\u201337 (2022)","journal-title":"J. Mach. Learn. Res."},{"key":"2213_CR44","unstructured":"Correa, J., D\u00fctting, P., Fischer, F., Schewior, K.: Prophet inequalities for iid random variables from an unknown distribution. Mathematics of Operations Research (2021)"},{"key":"2213_CR45","unstructured":"Rubinstein, A., Wang, J.Z., Weinberg, S.M.: Optimal single-choice prophet inequalities from samples. In: ITCS 2020, vol. 151, pp. 60\u201316010 (2020)"},{"key":"2213_CR46","doi-asserted-by":"crossref","unstructured":"Kaplan, H., Naori, D., Raz, D.: Online weighted matching with a sample (2022)","DOI":"10.1137\/1.9781611977073.52"},{"key":"2213_CR47","unstructured":"Brubach, B., Sankararaman, K.A., Srinivasan, A., Xu, P.: New algorithms, better bounds, and a novel model for online stochastic matching. In: ESA 2016 (2016)"},{"issue":"4","key":"2213_CR48","doi-asserted-by":"publisher","first-page":"1593","DOI":"10.1214\/aop\/1176991996","volume":"15","author":"U Krengel","year":"1987","unstructured":"Krengel, U., Sucheston, L.: Prophet compared to gambler: an inequality for transforms of processes. Ann. Probab. 15(4), 1593\u20131599 (1987)","journal-title":"Ann. Probab."},{"key":"2213_CR49","doi-asserted-by":"crossref","unstructured":"Huang, Z., Shu, X., Yan, S.: The power of multiple choices in online stochastic matching. In: STOC 2022, pp. 91\u2013103 (2022)","DOI":"10.1145\/3519935.3520046"},{"issue":"1\u20132","key":"2213_CR50","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1007\/s10107-020-01544-8","volume":"190","author":"J Correa","year":"2021","unstructured":"Correa, J., Saona, R., Ziliotto, B.: Prophet secretary through blind strategies. Math. Program. 190(1\u20132), 483\u2013521 (2021)","journal-title":"Math. Program."},{"key":"2213_CR51","doi-asserted-by":"crossref","unstructured":"Bubna, A., Chiplunkar, A.: Prophet inequality: order selection beats random order. In: EC 2023, pp. 302\u2013336 (2023)","DOI":"10.1145\/3580507.3597687"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02213-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-025-02213-4","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02213-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T07:10:31Z","timestamp":1777360231000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-025-02213-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,13]]},"references-count":51,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["2213"],"URL":"https:\/\/doi.org\/10.1007\/s10107-025-02213-4","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,3,13]]},"assertion":[{"value":"31 July 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 February 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 March 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}