{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T06:26:05Z","timestamp":1742970365974,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030927011"},{"type":"electronic","value":"9783030927028"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-92702-8_16","type":"book-chapter","created":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T06:00:24Z","timestamp":1641016824000},"page":"252-274","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Contention Resolution, Matrix Scaling and\u00a0Fair Allocation"],"prefix":"10.1007","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[]},{"given":"Ilan Reuven","family":"Cohen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,1]]},"reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"Adamczyk, M., W\u0142odarczyk, M.: Random order contention resolution schemes. In: Foundations of Computer Science (FOCS), pp. 790\u2013801 (2018)","DOI":"10.1109\/FOCS.2018.00080"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Bansal, N., Srinivasan, A., Svensson, O.: Lift-and-round to improve weighted completion time on unrelated machines. In: Symposium on Theory of Computing, STOC, pp. 156\u2013167 (2016)","DOI":"10.1145\/2897518.2897572"},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"Bansal, N., Sviridenko, M.: The santa claus problem. In: Symposium on Theory of Computing, STOC, pp. 31\u201340. ACM (2006)","DOI":"10.1145\/1132516.1132522"},{"key":"16_CR4","unstructured":"Bertsekas, D., Gallagher, R.: Data Networks. Prentice Hall, Hoboken (1992)"},{"key":"16_CR5","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"S Boyd","year":"2004","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, New York (2004)"},{"key":"16_CR6","doi-asserted-by":"crossref","unstructured":"Charikar, M.: Greedy approximation algorithms for finding dense components in a graph. In: APPROX, pp. 84\u201395 (2000)","DOI":"10.1007\/3-540-44436-X_10"},{"key":"16_CR7","doi-asserted-by":"crossref","unstructured":"Charikar, M., Makarychev, K., Makarychev, Y.: Near-optimal algorithms for unique games. In: Symposium on Theory of Computing, STOC, pp. 205\u2013214 (2006)","DOI":"10.1145\/1132516.1132547"},{"issue":"6","key":"16_CR8","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."},{"key":"16_CR9","doi-asserted-by":"crossref","unstructured":"Cohen, M.B., Madry, A., Tsipras, D., Vladu, A.: Matrix scaling and balancing via box constrained newton\u2019s method and interior point methods. In: Symposium on Foundations of Computer Science, FOCS, pp. 902\u2013913 (2017)","DOI":"10.1109\/FOCS.2017.88"},{"key":"16_CR10","volume-title":"Theory and Applications of Games of Strategy","author":"M Dresher","year":"1951","unstructured":"Dresher, M.: Theory and Applications of Games of Strategy. RAND Corporation, Santa Monica (1951)"},{"key":"16_CR11","doi-asserted-by":"crossref","unstructured":"Feige, U., Vondr\u00e1k, J.: Approximation algorithms for allocation problems: improving the factor of 1\u20131\/e. In: Symposium on Foundations of Computer Science, FOCS, pp. 667\u2013676 (2006)","DOI":"10.1109\/FOCS.2006.14"},{"issue":"1","key":"16_CR12","doi-asserted-by":"publisher","first-page":"247","DOI":"10.4086\/toc.2010.v006a011","volume":"6","author":"U Feige","year":"2010","unstructured":"Feige, U., Vondr\u00e1k, J.: The submodular welfare problem with demand queries. Theor. Comput. 6(1), 247\u2013290 (2010)","journal-title":"Theor. Comput."},{"key":"16_CR13","doi-asserted-by":"crossref","unstructured":"Feldman, M., Svensson, O., Zenklusen, R.: Online contention resolution schemes. In: Symposium on Discrete Algorithms, SODA, pp. 1014\u20131033 (2016)","DOI":"10.1137\/1.9781611974331.ch72"},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"Hensher, D.A., Rose, J.M., Greene, W.H.: Applied Choice Analysis. Cambridge University Press, Cambridge (2015)","DOI":"10.1017\/CBO9781316136232"},{"key":"16_CR15","doi-asserted-by":"crossref","unstructured":"Im, S., Shadloo, M.: Weighted completion time minimization for unrelated machines via iterative fair contention resolution. In: Symposium on Discrete Algorithms, SODA, pp. 2790\u20132809 (2020)","DOI":"10.1137\/1.9781611975994.170"},{"key":"16_CR16","doi-asserted-by":"publisher","first-page":"620","DOI":"10.1103\/PhysRev.106.620","volume":"106","author":"ET Jaynes","year":"1957","unstructured":"Jaynes, E.T.: Information theory and statistical mechanics. Phys. Rev. 106, 620\u2013630 (1957)","journal-title":"Phys. Rev."},{"key":"16_CR17","doi-asserted-by":"crossref","unstructured":"Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: Foundations of Computer Science, FOCS, pp. 312\u2013320 (1982)","DOI":"10.1109\/SFCS.1982.61"},{"issue":"3","key":"16_CR18","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1057\/palgrave.jors.2600523","volume":"49","author":"FP Kelly","year":"1998","unstructured":"Kelly, F.P., Maulloo, A.K., Tan, D.K.: Rate control for communication networks: shadow prices, proportional fairness and stability. J. Oper. Res. Soc. 49(3), 237\u2013252 (1998)","journal-title":"J. Oper. Res. Soc."},{"issue":"1","key":"16_CR19","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1137\/0120009","volume":"20","author":"E Kohlberg","year":"1971","unstructured":"Kohlberg, E.: On the nucleolus of a characteristic function game. SIAM J. Appl. Math. 20(1), 62\u201366 (1971)","journal-title":"SIAM J. Appl. Math."},{"key":"16_CR20","unstructured":"Lee, E., Singla, S.: Optimal online contention resolution schemes via ex-ante prophet inequalities. In: European Symposium on Algorithms, ESA, volume 112 of LIPIcs, pp. 57:1\u201357:14 (2018)"},{"issue":"4","key":"16_CR21","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1007\/s004930070007","volume":"20","author":"N Linial","year":"2000","unstructured":"Linial, N., Samorodnitsky, A., Wigderson, A.: A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents. Combinatorica 20(4), 545\u2013568 (2000)","journal-title":"Combinatorica"},{"key":"16_CR22","volume-title":"Individual Choice Behavior: A Theoretical Analysis","author":"RD Luce","year":"1959","unstructured":"Luce, R.D.: Individual Choice Behavior: A Theoretical Analysis. Wiley, New York (1959)"},{"key":"16_CR23","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1016\/0024-3795(89)90491-6","volume":"114","author":"UG Rothblum","year":"1989","unstructured":"Rothblum, U.G., Schneider, H.: Scalings of matrices which have prespecified row sums and column sums via optimization. Linear Algebra Appl. 114, 737\u2013764 (1989)","journal-title":"Linear Algebra Appl."},{"key":"16_CR24","doi-asserted-by":"crossref","unstructured":"Singh, M., Vishnoi, N.K.: Entropy, optimization and counting. In: Symposium on Theory of Computing, STOC, pp. 50\u201359 (2014)","DOI":"10.1145\/2591796.2591803"},{"issue":"2","key":"16_CR25","doi-asserted-by":"publisher","first-page":"876","DOI":"10.1214\/aoms\/1177703591","volume":"35","author":"R Sinkhorn","year":"1964","unstructured":"Sinkhorn, R.: A relationship between arbitrary positive matrices and doubly stochastic matrices. Ann. Math. Stat. 35(2), 876\u2013879 (1964)","journal-title":"Ann. Math. Stat."},{"key":"16_CR26","unstructured":"Train, K.E.: Discrete Choice Methods with Simulation. Cambridge University Press, Cambridge (2009)"},{"key":"16_CR27","doi-asserted-by":"crossref","unstructured":"Wainwright, M.J., Jordan, M.I.: Graphical models, exponential families, and variational Inference. Found. Trends\u00ae Mach. Learn. 1(1\u20132), 1\u2013305 (2008)","DOI":"10.1561\/2200000001"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-92702-8_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T06:23:06Z","timestamp":1641018186000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-92702-8_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030927011","9783030927028"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-92702-8_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"1 January 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WAOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Approximation and Online Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Lisbon","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Portugal","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 September 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 September 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"waoa2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/algo2021.tecnico.ulisboa.pt\/WAOA2021\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-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":"31","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":"16","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":"52% - 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":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}