{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,29]],"date-time":"2024-12-29T07:10:05Z","timestamp":1735456205728,"version":"3.32.0"},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1996,12,1]],"date-time":"1996-12-01T00:00:00Z","timestamp":849398400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1996,12]]},"DOI":"10.1007\/bf01271265","type":"journal-article","created":{"date-parts":[[2005,3,24]],"date-time":"2005-03-24T04:35:40Z","timestamp":1111638940000},"page":"453-464","source":"Crossref","is-referenced-by-count":0,"title":["Distributed near-optimal matching"],"prefix":"10.1007","volume":"16","author":[{"given":"Xiaotie","family":"Deng","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","volume-title":"Probabilistic Method","author":"N. Alon","year":"1992","unstructured":"N. Alon, andJ. H. Spencer:Probabilistic Method, Viley-Interscience Publication, John Wiley & Sons, Inc. Toronto, 1992."},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"A. Blum, andP. Chalasani: An Online Algorithm for Improving Performance in Navigation,FOCS93, (1993), 2?11.","DOI":"10.1109\/SFCS.1993.366887"},{"key":"CR3","volume-title":"Extremal Graph Theory","author":"B. Bollob\u00e1s","year":"1978","unstructured":"B. Bollob\u00e1s:Extremal Graph Theory, Academic Press Inc. New York, 1978."},{"key":"CR4","unstructured":"X. Deng, andC. Papadimitriou: Competitive Distributed Decision-Making,Proc. 12th IFIP Congress, Madrid, September 1993. And also to appear in Algorithmica."},{"key":"CR5","volume-title":"Ramsey Theory","author":"R. L. Graham","year":"1980","unstructured":"R. L. Graham, B. L. Rothschild,and J. H. Spencer:Ramsey Theory, John Wiley & Sons, New York, 1980."},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"S. Irani,and Y. Rabani: On the Value of Information in Coordination Games.FOCS93, (1993), 12?21.","DOI":"10.1109\/SFCS.1993.366886"},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"E. Koutsoupias,and C. H. Papadimitriou: On thek-server conjecture,Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, (1994) 507?511.","DOI":"10.1145\/195058.195245"},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"R. Karp, U. V. Vazirani,and V.V. Varirani: An Optimal Algorithm for Online Bipartite Matching,Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, (1990), 352?358.","DOI":"10.1145\/100216.100262"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1016\/0196-6774(90)90003-W","volume":"11","author":"M. S. Manasse","year":"1990","unstructured":"M. S. Manasse, L. A. McGeoch,and D.D. Sleator: Competitive algorithms for on-line problems,Journal of Algorithms,11 (1990), 208?230.","journal-title":"Journal of Algorithms"},{"key":"CR10","first-page":"121","volume":"25","author":"C. H. Papadimitriou","year":"1993","unstructured":"C. H. Papadimitriou,and M. Yannakakis: Linear Programming without the Matrix,STOC,25 (1993), 121?129.","journal-title":"STOC"},{"key":"CR11","unstructured":"P. Raghavan:Lecture Notes on Randomized Algorithms, IRM Research Report, 1990, RC15340(#68237)1\/9\/90."},{"issue":"2","key":"CR12","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D. D. Sleator","year":"1985","unstructured":"D. D. Sleator,and R. E. Tarjan: Amortized efficiency of list update and paging rules,Communications of the ACM,28:2 (1985), 202?208.","journal-title":"Communications of the ACM"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01271265.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01271265\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01271265","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,28]],"date-time":"2024-12-28T09:10:12Z","timestamp":1735377012000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01271265"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,12]]},"references-count":12,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1996,12]]}},"alternative-id":["BF01271265"],"URL":"https:\/\/doi.org\/10.1007\/bf01271265","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"type":"print","value":"0209-9683"},{"type":"electronic","value":"1439-6912"}],"subject":[],"published":{"date-parts":[[1996,12]]}}}