{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:35:35Z","timestamp":1767339335975,"version":"3.40.3"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030179526"},{"type":"electronic","value":"9783030179533"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-17953-3_18","type":"book-chapter","created":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T23:25:20Z","timestamp":1556753120000},"page":"233-246","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["The Markovian Price of Information"],"prefix":"10.1007","author":[{"given":"Anupam","family":"Gupta","sequence":"first","affiliation":[]},{"given":"Haotian","family":"Jiang","sequence":"additional","affiliation":[]},{"given":"Ziv","family":"Scully","sequence":"additional","affiliation":[]},{"given":"Sahil","family":"Singla","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,4,13]]},"reference":[{"key":"18_CR1","unstructured":"Abbas, A.E., Howard, R.A.: Foundations of Decision Analysis. Pearson Higher Ed. London (2015)"},{"issue":"4","key":"18_CR2","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"},{"issue":"4","key":"18_CR3","doi-asserted-by":"publisher","first-page":"785","DOI":"10.1006\/jcss.2002.1828","volume":"64","author":"M Charikar","year":"2002","unstructured":"Charikar, M., Fagin, R., Guruswami, V., Kleinberg, J.M., Raghavan, P., Sahai, A.: Query strategies for priced information. J. Comput. Syst. Sci. 64(4), 785\u2013819 (2002). https:\/\/doi.org\/10.1006\/jcss.2002.1828","journal-title":"J. Comput. Syst. Sci."},{"key":"18_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/978-3-642-02927-1_23","volume-title":"Automata, Languages and Programming","author":"N Chen","year":"2009","unstructured":"Chen, N., Immorlica, N., Karlin, A.R., Mahdian, M., Rudra, A.: Approximating matches made in heaven. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol. 5555, pp. 266\u2013278. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-02927-1_23"},{"key":"18_CR5","doi-asserted-by":"crossref","unstructured":"Chen, Y., Immorlica, N., Lucier, B., Syrgkanis, V., Ziani, J.: Optimal data acquisition for statistical estimation. arXiv preprint arXiv:1711.01295 (2017)","DOI":"10.1145\/3219166.3219195"},{"key":"18_CR6","unstructured":"Chen, Y., Hassani, S.H., Karbasi, A., Krause, A.: Sequential information maximization: When is greedy near-optimal? In: Conference on Learning Theory, pp. 338\u2013363 (2015)"},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"Chen, Y., Javdani, S., Karbasi, A., Bagnell, J.A., Srinivasa, S.S., Krause, A.: Submodular surrogates for value of information. In: AAAI, pp. 3511\u20133518 (2015)","DOI":"10.1609\/aaai.v29i1.9694"},{"issue":"4","key":"18_CR8","doi-asserted-by":"publisher","first-page":"604","DOI":"10.1137\/S0895480102408341","volume":"16","author":"I Dumitriu","year":"2003","unstructured":"Dumitriu, I., Tetali, P., Winkler, P.: On playing golf with two balls. SIAM J. Discrete Math. 16(4), 604\u2013615 (2003)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"18_CR9","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":"18_CR10","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. Society for Industrial and Applied Mathematics (2016)","DOI":"10.1137\/1.9781611974331.ch72"},{"key":"18_CR11","doi-asserted-by":"publisher","DOI":"10.1002\/9780470980033","volume-title":"Multi-Armed Bandit Allocation Indices","author":"J Gittins","year":"2011","unstructured":"Gittins, J., Glazebrook, K., Weber, R.: Multi-Armed Bandit Allocation Indices. Wiley, Chichester (2011)"},{"key":"18_CR12","first-page":"241","volume-title":"Progress in Statistics","author":"J Gittins","year":"1974","unstructured":"Gittins, J., Jones, D.: A dynamic allocation index for the sequential design of experiments. In: Gani, J. (ed.) Progress in Statistics, pp. 241\u2013266. North-Holland, Amsterdam (1974)"},{"key":"18_CR13","doi-asserted-by":"crossref","unstructured":"Guha, S., Munagala, K.: Approximation algorithms for budgeted learning problems. In: STOC, pp. 104\u2013113 (2007), full version as: Approximation Algorithms for Bayesian Multi-Armed Bandit Problems. http:\/\/arxiv.org\/abs\/1306.3525","DOI":"10.1145\/1250790.1250807"},{"key":"18_CR14","unstructured":"Guha, S., Munagala, K., Sarkar, S.: Information acquisition and exploitation in multichannel wireless systems. In: IEEE Transactions on Information Theory. Citeseer (2007)"},{"key":"18_CR15","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kumar, A.: Sorting and selection with structured costs. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, 2001, pp. 416\u2013425. IEEE (2001)","DOI":"10.1109\/SFCS.2001.959916"},{"key":"18_CR16","unstructured":"Kannan, S., Khanna, S.: Selection with monotone comparison costs. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete algorithms, pp. 10\u201317. Society for Industrial and Applied Mathematics (2003)"},{"key":"18_CR17","doi-asserted-by":"crossref","unstructured":"Kleinberg, R., Waggoner, B., Weyl, G.: Descending Price Optimally Coordinates Search. arXiv preprint arXiv:1603.07682 (2016)","DOI":"10.2139\/ssrn.2810329"},{"key":"18_CR18","doi-asserted-by":"crossref","unstructured":"Singla, S.: The price of information in combinatorial optimization. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM (2018)","DOI":"10.1137\/1.9781611975031.161"},{"key":"18_CR19","doi-asserted-by":"crossref","unstructured":"Tsitsiklis, J.N.: A short proof of the Gittins index theorem. The Annals of Applied Probability, pp. 194\u2013199 (1994)","DOI":"10.1214\/aoap\/1177005207"},{"issue":"4","key":"18_CR20","doi-asserted-by":"publisher","first-page":"1024","DOI":"10.1214\/aoap\/1177005588","volume":"2","author":"R Weber","year":"1992","unstructured":"Weber, R.: On the Gittins index for multiarmed bandits. Ann. Appl. Probab. 2(4), 1024\u20131033 (1992)","journal-title":"Ann. Appl. Probab."},{"issue":"2","key":"18_CR21","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1111\/j.2517-6161.1980.tb01111.x","volume":"42","author":"P. Whittle","year":"1980","unstructured":"Whittle, P.: Multi-armed bandits and the Gittins index. J. Roy. Stat. Soc. Ser. B (Methodol.), 143\u2013149 (1980)","journal-title":"Journal of the Royal Statistical Society: Series B (Methodological)"}],"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-030-17953-3_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,17]],"date-time":"2024-07-17T14:37:48Z","timestamp":1721227068000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-17953-3_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030179526","9783030179533"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-17953-3_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"13 April 2019","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":"Ann Arbor, MI","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 May 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 May 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/umich.edu\/~ipco2019conf\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"113","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"33","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"29% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2.5","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}