{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:12:55Z","timestamp":1759637575031,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2019,3,15]],"date-time":"2019-03-15T00:00:00Z","timestamp":1552608000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,3,15]],"date-time":"2019-03-15T00:00:00Z","timestamp":1552608000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["16K16011","16H06931"],"award-info":[{"award-number":["16K16011","16H06931"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2020,7]]},"DOI":"10.1007\/s10107-019-01388-x","type":"journal-article","created":{"date-parts":[[2019,3,15]],"date-time":"2019-03-15T15:04:07Z","timestamp":1552662247000},"page":"141-174","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Stochastic packing integer programs with few queries"],"prefix":"10.1007","volume":"182","author":[{"given":"Takanori","family":"Maehara","sequence":"first","affiliation":[]},{"given":"Yutaro","family":"Yamaguchi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,3,15]]},"reference":[{"issue":"15","key":"1388_CR1","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1016\/j.ipl.2011.05.007","volume":"111","author":"M Adamczyk","year":"2011","unstructured":"Adamczyk, M.: Improved analysis of the greedy algorithm for stochastic matching. Inf. Process. Lett. 111(15), 731\u2013737 (2011)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"1388_CR2","doi-asserted-by":"publisher","first-page":"1022","DOI":"10.1287\/moor.2015.0766","volume":"41","author":"M Adamczyk","year":"2016","unstructured":"Adamczyk, M., Sviridenko, M., Ward, J.: Submodular stochastic probing on matroids. Math. Oper. Res. 41(3), 1022\u20131038 (2016)","journal-title":"Math. Oper. Res."},{"key":"1388_CR3","doi-asserted-by":"crossref","unstructured":"Assadi, S., Khanna, S., Li, Y.: The stochastic matching problem with (very) few queries. In: Proceedings of the 17th ACM Conference on Economics and Computation, pp. 43\u201360. ACM (2016)","DOI":"10.1145\/2940716.2940769"},{"key":"1388_CR4","doi-asserted-by":"crossref","unstructured":"Assadi, S., Khanna, S., Li, Y.: The stochastic matching problem: beating half with a non-adaptive algorithm. In: Proceedings of the 18th ACM Conference on Economics and Computation, pp. 99\u2013116. ACM (2017)","DOI":"10.1145\/3033274.3085146"},{"issue":"4","key":"1388_CR5","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1007\/s00453-011-9511-8","volume":"63","author":"N Bansal","year":"2012","unstructured":"Bansal, N., Gupta, A., Li, J., Mestre, J., Nagarajan, V., Rudra, A.: When LP is the cure for your matching woes: improved bounds for stochastic matchings. Algorithmica 63(4), 733\u2013762 (2012)","journal-title":"Algorithmica"},{"key":"1388_CR6","doi-asserted-by":"crossref","unstructured":"Behnezhad, S., Reyhani, N.: Almost optimal stochastic weighted matching with few queries In: Proceedings of the 19th ACM Conference on Economics and Computation, pp. 235\u2013249. ACM (2018)","DOI":"10.1145\/3219166.3219226"},{"key":"1388_CR7","doi-asserted-by":"crossref","unstructured":"Blum, A., Dickerson, J.P., Haghtalab, N., Procaccia, A.D., Sandholm, T., Sharma, A.: Ignorance is almost bliss: near-optimal stochastic matching with few queries. In: Proceedings of the 16th ACM Conference on Economics and Computation, pp. 325\u2013342. ACM (2015)","DOI":"10.1145\/2764468.2764479"},{"key":"1388_CR8","doi-asserted-by":"crossref","unstructured":"Blum, A., Gupta, A., Procaccia, A., Sharma, A.: Harnessing the power of two crossmatches. In: Proceedings of the 14th ACM conference on Electronic Commerce, pp. 123\u2013140. ACM (2013)","DOI":"10.1145\/2482540.2482569"},{"key":"1388_CR9","doi-asserted-by":"crossref","unstructured":"Chan, Y.H., Lau, L.C.: On linear and semidefinite programming relaxations for hypergraph matching. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1500\u20131511. SIAM (2010)","DOI":"10.1137\/1.9781611973075.122"},{"key":"1388_CR10","doi-asserted-by":"crossref","unstructured":"Chen, N., Immorlica, N., Karlin, A.R., Mahdian, M., Rudra, A.: Approximating matches made in heaven. In: Proceedings of the 36th International Colloquium on Automata, Languages, and Programming, pp. 266\u2013278. Springer (2009)","DOI":"10.1007\/978-3-642-02927-1_23"},{"key":"1388_CR11","doi-asserted-by":"crossref","unstructured":"Chitnis, R., Cormode, G., Esfandiari, H., Hajiaghayi, M., McGregor, A., Monemizadeh, M., Vorotnikova, S.: Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1326\u20131344. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch92"},{"key":"1388_CR12","doi-asserted-by":"crossref","unstructured":"Costello, K., Tetali, P., Tripathi, P.: Stochastic matching with commitment. In: Proceedings of the 39th International Colloquium on Automata, Languages and Programming, pp. 822\u2013833. Springer (2012)","DOI":"10.1007\/978-3-642-31594-7_69"},{"key":"1388_CR13","doi-asserted-by":"crossref","unstructured":"Cunningham, W.H., Marsh, A.B.: A primal algorithm for optimum matching. Polyhedral Combinatorics pp. 50\u201372 (1978)","DOI":"10.1007\/BFb0121194"},{"key":"1388_CR14","unstructured":"Dean, B.C., Goemans, M.X., Vondr\u00e1k, J.: Approximating the stochastic knapsack problem: the benefit of adaptivity. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 208\u2013217. IEEE (2004)"},{"key":"1388_CR15","unstructured":"Dean, B.C., Goemans, M.X., Vondr\u00e1k, J.: Adaptivity and approximation for stochastic packing problems. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 395\u2013404. SIAM (2005)"},{"key":"1388_CR16","unstructured":"Dickerson, J.P., Sandholm, T.: Organ exchanges: a success story of AI in healthcare. In: 30th Conference on Artificial Intelligence Tutorial Forum (2016)"},{"key":"1388_CR17","volume-title":"Parameterized Complexity","author":"RG Downey","year":"2012","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (2012)"},{"key":"1388_CR18","unstructured":"Edmonds, J.: Submodular functions, matroids, and certain polyhedra. In: Proceedings of the Calgary International Conference on Combinatorial Structures and Their Applications, pp. 69\u201387. Gordon and Breach (1970)"},{"key":"1388_CR19","first-page":"16","volume":"38","author":"E Egerv\u00e1ry","year":"1931","unstructured":"Egerv\u00e1ry, E.: On combinatorial properties of matrices. Matematikai Lapok 38, 16\u201328 (1931)","journal-title":"Matematikai Lapok"},{"issue":"4","key":"1388_CR20","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1016\/j.jctb.2013.05.004","volume":"103","author":"D Gijswijt","year":"2013","unstructured":"Gijswijt, D., Pap, G.: An algorithm for weighted fractional matroid matching. J. Comb. Theory, Ser. B 103(4), 509\u2013520 (2013)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"1388_CR21","doi-asserted-by":"crossref","unstructured":"Gupta, A., Nagarajan, V.: A stochastic probing problem with applications. In: Proceedings of the 16th International Conference on Integer Programming and Combinatorial Optimization, pp. 205\u2013216. Springer (2013)","DOI":"10.1007\/978-3-642-36694-9_18"},{"key":"1388_CR22","doi-asserted-by":"crossref","unstructured":"Gupta, A., Nagarajan, V., Singla, S.: Adaptivity gaps for stochastic probing: submodular and XOS functions. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1688\u20131702. SIAM (2017)","DOI":"10.1137\/1.9781611974782.111"},{"issue":"1","key":"1388_CR23","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1137\/0402008","volume":"2","author":"CAJ Hurkens","year":"1989","unstructured":"Hurkens, C.A.J., Schrijver, A.: On the size of systems of sets every $$t$$ of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems. SIAM J. Discret. Math. 2(1), 68\u201372 (1989)","journal-title":"SIAM J. Discret. Math."},{"issue":"6","key":"1388_CR24","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1007\/s00493-012-2760-6","volume":"32","author":"T Kir\u00e1ly","year":"2012","unstructured":"Kir\u00e1ly, T., Lau, L.C., Singh, M.: Degree bounded matroids and submodular flows. Combinatorica 32(6), 703\u2013720 (2012)","journal-title":"Combinatorica"},{"issue":"4","key":"1388_CR25","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1016\/j.jcss.2005.05.002","volume":"71","author":"SG Kolliopoulos","year":"2005","unstructured":"Kolliopoulos, S.G., Young, N.E.: Approximation algorithms for covering\/packing integer programs. J. Comput. Syst. Sci. 71(4), 495\u2013505 (2005)","journal-title":"J. Comput. Syst. Sci."},{"key":"1388_CR26","first-page":"116","volume":"38","author":"D K\u0151nig","year":"1931","unstructured":"K\u0151nig, D.: Graphs and matrices. Math. Fiz. Lapok 38, 116\u2013119 (1931)","journal-title":"Math. Fiz. Lapok"},{"issue":"1","key":"1388_CR27","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1137\/11083232X","volume":"42","author":"J Lee","year":"2013","unstructured":"Lee, J., Sviridenko, M., Vondr\u00e1k, J.: Matroid matching: the power of local search. SIAM J. Comput. 42(1), 357\u2013379 (2013)","journal-title":"SIAM J. Comput."},{"key":"1388_CR28","unstructured":"Molinaro, M., Ravi, R.: The query-commit problem. arXiv preprint \narXiv:1110.0990\n\n (2011)"},{"issue":"2","key":"1388_CR29","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1137\/S0097539793250767","volume":"26","author":"A Panconesi","year":"1997","unstructured":"Panconesi, A., Srinivasan, A.: Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds. SIAM J. Comput. 26(2), 350\u2013368 (1997)","journal-title":"SIAM J. Comput."},{"key":"1388_CR30","doi-asserted-by":"crossref","unstructured":"Parekh, O.: Iterative packing for demand and hypergraph matching. In: Proceedings of the 15th International Conference on Integer Programming and Combinatorial Optimization, pp. 349\u2013361. Springer (2011)","DOI":"10.1007\/978-3-642-20807-2_28"},{"key":"1388_CR31","doi-asserted-by":"crossref","unstructured":"Parekh, O., Pritchard, D.: Generalized hypergraph matching via iterated packing and local ratio. In: Proceedings of the 12th International Workshop on Approximation and Online Algorithms, pp. 207\u2013223. Springer (2014)","DOI":"10.1007\/978-3-319-18263-6_18"},{"issue":"4","key":"1388_CR32","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P Raghavan","year":"1987","unstructured":"Raghavan, P., Tompson, C.D.: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7(4), 365\u2013374 (1987)","journal-title":"Combinatorica"},{"issue":"2","key":"1388_CR33","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1162\/0033553041382157","volume":"119","author":"AE Roth","year":"2004","unstructured":"Roth, A.E., S\u00f6nmez, T., \u00dcnver, M.U.: Kidney exchange. Q. J. Econ. 119(2), 457\u2013488 (2004)","journal-title":"Q. J. Econ."},{"key":"1388_CR34","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, Springer (2003)"},{"issue":"3","key":"1388_CR35","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1287\/moor.1070.0254","volume":"32","author":"FB Shepherd","year":"2007","unstructured":"Shepherd, F.B., Vetta, A.: The demand-matching problem. Math. Oper. Res. 32(3), 563\u2013578 (2007)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"1388_CR36","doi-asserted-by":"publisher","first-page":"19","DOI":"10.4064\/cm-3-1-19-30","volume":"3","author":"P Tur\u00e1n","year":"1954","unstructured":"Tur\u00e1n, P.: On the theory of graphs. Colloquium Mathematicae 3(1), 19\u201330 (1954)","journal-title":"Colloquium Mathematicae"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01388-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-019-01388-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01388-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,23]],"date-time":"2020-06-23T15:14:23Z","timestamp":1592925263000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-019-01388-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,15]]},"references-count":36,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["1388"],"URL":"https:\/\/doi.org\/10.1007\/s10107-019-01388-x","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2019,3,15]]},"assertion":[{"value":"16 February 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 March 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 March 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}