{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T15:57:22Z","timestamp":1780675042195,"version":"3.54.1"},"reference-count":111,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0746673"],"award-info":[{"award-number":["CCF-0746673"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-1217338"],"award-info":[{"award-number":["CCF-1217338"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100005156","name":"Alexander von Humboldt-Stiftung","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100005156","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>\n            The\n            <jats:italic>maximum cardinality<\/jats:italic>\n            and\n            <jats:italic>maximum weight matching<\/jats:italic>\n            problems can be solved in\n            <jats:italic>\u00d5<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            \u221a\n            <jats:italic>n<\/jats:italic>\n            ) time, a bound that has resisted improvement despite decades of research. (Here\n            <jats:italic>m<\/jats:italic>\n            and\n            <jats:italic>n<\/jats:italic>\n            are the number of edges and vertices.) In this article, we demonstrate that this \u201c\n            <jats:italic>m<\/jats:italic>\n            \u221a\n            <jats:italic>n<\/jats:italic>\n            barrier\u201d can be bypassed by approximation. For any\n            <jats:italic>\u03b5<\/jats:italic>\n            &gt; 0, we give an algorithm that computes a (1 \u2212\n            <jats:italic>\u03b5<\/jats:italic>\n            )-approximate maximum weight matching in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m\u03b5<\/jats:italic>\n            <jats:sup>\u22121<\/jats:sup>\n            log\n            <jats:italic>\u03b5<\/jats:italic>\n            <jats:sup>\u22121<\/jats:sup>\n            ) time, that is, optimal\n            <jats:italic>linear time<\/jats:italic>\n            for any fixed\n            <jats:italic>\u03b5<\/jats:italic>\n            . Our algorithm is dramatically simpler than the best exact maximum weight matching algorithms on general graphs and should be appealing in all applications that can tolerate a negligible relative error.\n          <\/jats:p>","DOI":"10.1145\/2529989","type":"journal-article","created":{"date-parts":[[2014,2,4]],"date-time":"2014-02-04T14:16:21Z","timestamp":1391523381000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":163,"title":["Linear-Time Approximation for Maximum Weight Matching"],"prefix":"10.1145","volume":"61","author":[{"given":"Ran","family":"Duan","sequence":"first","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Seth","family":"Pettie","sequence":"additional","affiliation":[{"name":"University of Michigan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90195-N"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/161541.161736"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1580"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 9th Southeast Conference on Combinatorics, Graph Theory, and Computing (CongrNumer XXI). 65--76","author":"Avis D.","year":"1978","unstructured":"Avis, D. 1978. Two greedy heuristics for the weighted matching problems. In Proceedings of the 9th Southeast Conference on Combinatorics, Graph Theory, and Computing (CongrNumer XXI). 65--76."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130404"},{"key":"e_1_2_1_6_1","volume-title":"Labelling to obtain a maximum matching","author":"Balinski M. L.","unstructured":"Balinski, M. L. 1969. Labelling to obtain a maximum matching. In Combinatorial Mathematics and Its Applications, R. C. Bose and T. A. Downing Eds., University of North Carolina Press, 585--602."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584237"},{"key":"e_1_2_1_8_1","first-page":"1","article-title":"Tres observaciones sobre el elgebra lineal. Universidad Nacional de Tucuman","volume":"5","author":"Birkhoff G.","year":"1946","unstructured":"Birkhoff, G. 1946. Tres observaciones sobre el elgebra lineal. Universidad Nacional de Tucuman, Revista A 5, 1--2, 147--151.","journal-title":"Revista A"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289295"},{"key":"e_1_2_1_10_1","volume-title":"Contributions to the Theory of Games","author":"Brown G.","unstructured":"Brown, G. and von Neumann, J. 1950. Solutions of games by differential equations. In Contributions to the Theory of Games, H. Kuhn and A. Tucker Eds., Annals of Mathematical Studies Series, vol. 24. Princeton University Press, 73--79."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940880"},{"key":"e_1_2_1_12_1","volume-title":"Graduate School of Industrial Administration","author":"Christofides N.","unstructured":"Christofides, N. 1976. Worst case analysis of a new heuristic for the travelling salesman problem. Tech. rep., Graduate School of Industrial Administration, Carnegie Mellon University."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/365411.365414"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0121194"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.72"},{"key":"e_1_2_1_16_1","volume-title":"Activity Analysis of Production and Allocation, Cowles Commission Monograph 13","author":"Dantzig G. B.","unstructured":"Dantzig, G. B. 1951. Application of the simplex method to the transportation problem. In Activity Analysis of Production and Allocation, Cowles Commission Monograph 13, T. C. Koopmans Ed., Wiley, New York, 359--373."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.17.6.1017"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_19_1","first-page":"1277","article-title":"Algorithm for solution of a problem of maximum flow in networks with power estimation","volume":"11","author":"Dinic E. A.","year":"1970","unstructured":"Dinic, E. A. 1970. Algorithm for solution of a problem of maximum flow in networks with power estimation. Soviet Math. Dokl. 11, 1277--1280.","journal-title":"Soviet Math. Dokl."},{"key":"e_1_2_1_20_1","first-page":"1324","article-title":"An algorithm for the solution of the assignment problem","volume":"10","author":"Dinic E. A.","year":"1969","unstructured":"Dinic, E. A. and Kronrod, M. A. 1969. An algorithm for the solution of the assignment problem. Soviet Math. Dokl. 10, 6, 1324--1326.","journal-title":"Soviet Math. Dokl."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45198-3_2"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00393-9"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.70"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095227"},{"key":"e_1_2_1_25_1","volume-title":"Householder Symposium XV Book of Abstracts, 73--75","author":"Duff I. S.","unstructured":"Duff, I. S. and Gilbert, J. R. 2002. Maximum-weighted matching and block pivoting for symmetric indefinite systems. In Householder Symposium XV Book of Abstracts, 73--75."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-21.3.219"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.069B.013"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580113"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321699"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1065"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Ford L. R. and Fulkerson D. R. 1962. Flows in Networks. Princeton University Press.","DOI":"10.1515\/9781400875184"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.3"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90039-X"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/320176.320229"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/645901.758331"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90014-5"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218069"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/115234.115366"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65954"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215009"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the 24th INFOCOM.","volume":"2","author":"Giaccone P.","unstructured":"Giaccone, P., Leonardi, E., and Shah, D. 2005. On the maximal throughput of networks with finite buffers and its application to buffered crossbars. In Proceedings of the 24th INFOCOM. Vol. 2, 971--980."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.054.025"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0505-z"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480194281185"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204019"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/040615614"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509993"},{"key":"e_1_2_1_52_1","unstructured":"Hanke S. and Hougardy S. 2010. New approximation algorithms for the weighted matching problem. Research rep. No. 101010 Research Institute for Discrete Mathematics University of Bonn."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/070684008"},{"key":"e_1_2_1_54_1","unstructured":"Hendrickson B. and Leland R. 1995. The Chaco user\u2019s guide: Version 2.0. Tech. rep. SAND94--2344 Sandia National Laboratories."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1002\/sapm1941201224"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800100132"},{"key":"e_1_2_1_57_1","volume-title":"Proceedings of the 24th IEEE Symposium on Parallel and Distributed Processing (IPDPS). 1--12","author":"Holtgrewe M.","unstructured":"Holtgrewe, M., Sanders, P., and Schulz, C. 2010. Engineering a scalable high quality graph partitioner. In Proceedings of the 24th IEEE Symposium on Parallel and Distributed Processing (IPDPS). 1--12."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095226"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90142-3"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130105"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(75)90001-0"},{"key":"e_1_2_1_63_1","first-page":"199","article-title":"On the translocation of masses","volume":"37","author":"Kantorovitch L.","year":"1942","unstructured":"Kantorovitch, L. 1942. On the translocation of masses. Doklady Akad. Nauk SSSR 37, 199--201.","journal-title":"Doklady Akad. Nauk SSSR"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799361208"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_2_1_66_1","first-page":"66","article-title":"An exact estimate of an algorithm for finding a maximum flow, applied to the problem \u201con representatives","volume":"5","author":"Karzanov A. V.","year":"1973","unstructured":"Karzanov, A. V. 1973. An exact estimate of an algorithm for finding a maximum flow, applied to the problem \u201con representatives\u201d {in Russian}. Probl. Cybernetics 5, 66--70. (English translation available at the author\u2019s website.)","journal-title":"{in Russian}. Probl. Cybernetics"},{"key":"e_1_2_1_67_1","volume-title":"Efficient implementations of Edmonds","author":"Karzanov A. V.","unstructured":"Karzanov, A. V. 1976. Efficient implementations of Edmonds\u2019 algorithms for finding matchings with maximum cardinality and maximum weight. In Studies in Discrete Optimization, A. A. Fridman Ed., Nauka, Moscow, 306--327."},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800020109"},{"key":"e_1_2_1_69_1","first-page":"1","article-title":"On combinatorial properties of matrices","volume":"11","author":"Kuhn H. W.","year":"1955","unstructured":"Kuhn, H. W. 1955b. On combinatorial properties of matrices. George Washington University Logistics Papers 11, 1--11. (English translation of J. Egerv\u00e1ry, Matrixok kombinatorius tulajdons\u00e1gair\u00f3l, Matematikai \u00e9s Fizikai Lapok 38, 16--28, 1931.)","journal-title":"George Washington University Logistics Papers"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800030404"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800090102"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/321138.321140"},{"key":"e_1_2_1_73_1","first-page":"273","article-title":"Graphic programming using odd or even points","volume":"1","author":"Kwan M. K.","year":"1962","unstructured":"Kwan, M. K. 1962. Graphic programming using odd or even points. Chinese Math. 1, 273--277.","journal-title":"Chinese Math."},{"key":"e_1_2_1_74_1","volume-title":"Combinatorial Optimization: Networks and Matroids. Holt, Rinehart & Winston","author":"Lawler E.","year":"1976","unstructured":"Lawler, E. 1976. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart & Winston, New York."},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792544"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.769767"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.5555\/1895807.1895852"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1980.12"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1090\/psapm\/006\/0090480"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.40"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1137\/0105003"},{"key":"e_1_2_1_82_1","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1007\/s00200-009-0087-3","article-title":"Looking for the order of a system of arbitrary ordinary differential equations","volume":"20","author":"Ollivier F.","year":"2009","unstructured":"Ollivier, F. 2009. Looking for the order of a system of arbitrary ordinary differential equations. Appl. Algebra Eng. Commun. Comput. 20, 1, 7--32. (English translation of: C. G. J. Jacobi, De investigando ordine systematis aequationum differentialum vulgarium cujuscunque, Borchardt Journal f\u00fcr die reine und angewandte Mathematik 65, 4, pp. 297--320, 1865.)","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(94)00192-8"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01586040"},{"key":"e_1_2_1_85_1","first-page":"502","article-title":"Finding the maximum cut in a planar graph","volume":"10","author":"Orlova G. I.","year":"1972","unstructured":"Orlova, G. I. and Dorfman, Y. G. 1972. Finding the maximum cut in a planar graph. Eng. Cybernet. 10, 502--506.","journal-title":"Eng. Cybernet."},{"key":"e_1_2_1_86_1","unstructured":"Pellegrini F. 2008. SCOTCH 5.1 user\u2019s guide. Technical report LaBRI."},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1007\/11602613_96"},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2012.08.010"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.05.007"},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.5555\/1764891.1764924"},{"key":"e_1_2_1_91_1","doi-asserted-by":"crossref","unstructured":"Preis R. and Diekmann R. 1997. PARTY -- A software library for graph partitioning. In Advances in Computational Mechanics with Parallel and Distributed Processing B. H. V. Topping Ed. Civil-Comp Press 63--71.","DOI":"10.4203\/ccp.45.3.1"},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.9"},{"key":"e_1_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130104"},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210050"},{"key":"e_1_2_1_95_1","volume-title":"Proceedings of the 14th Workshop on Algorithm Engineering and Experiments (ALENEX). 43--54","author":"Sanders P.","unstructured":"Sanders, P. and Schulz, C. 2012. Distributed evolutionary graph partitioning. In Proceedings of the 14th Workshop on Algorithm Engineering and Experiments (ALENEX). 43--54."},{"key":"e_1_2_1_96_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.07.028"},{"key":"e_1_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-006-9003-y"},{"key":"e_1_2_1_98_1","doi-asserted-by":"publisher","DOI":"10.1109\/40.988685"},{"key":"e_1_2_1_99_1","volume-title":"Proceedings of the 21st INFOCOM. 1024--1031","author":"Shah D.","unstructured":"Shah, D. and Kopikare, M. 2002. Delay bounds for the approximate maximum weight matching algorithm for input queued switches. In Proceedings of the 21st INFOCOM. 1024--1031."},{"key":"e_1_2_1_100_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214014"},{"key":"e_1_2_1_101_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289039"},{"key":"e_1_2_1_102_1","doi-asserted-by":"publisher","DOI":"10.1145\/316542.316548"},{"key":"e_1_2_1_103_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780566"},{"key":"e_1_2_1_104_1","doi-asserted-by":"publisher","DOI":"10.1145\/1314690.1314692"},{"key":"e_1_2_1_105_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010206"},{"key":"e_1_2_1_106_1","doi-asserted-by":"publisher","DOI":"10.5555\/314500.314918"},{"key":"e_1_2_1_107_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305952"},{"key":"e_1_2_1_108_1","doi-asserted-by":"publisher","DOI":"10.1145\/1077464.1077472"},{"key":"e_1_2_1_109_1","volume-title":"Contributions to the Theory of Games","author":"von Neumann J.","unstructured":"von Neumann, J. 1953. A certain zero-sum two-person game equivalent to the optimal assignment problem. In Contributions to the Theory of Games, H. W. Kuhn and A. W. Tucker Eds., Vol. II, Princeton University Press, 5--12."},{"key":"e_1_2_1_110_1","volume-title":"JOSTLE: Parallel multilevel graph-partitioning software -- an overview. In Mesh Partitioning Techniques and Domain Decomposition Techniques, 27--58.","author":"Walshaw C.","year":"2007","unstructured":"Walshaw, C. and Cross, M. 2007. JOSTLE: Parallel multilevel graph-partitioning software -- an overview. In Mesh Partitioning Techniques and Domain Decomposition Techniques, 27--58."},{"key":"e_1_2_1_111_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214056"},{"key":"e_1_2_1_112_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.069B.009"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2529989","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2529989","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:09:52Z","timestamp":1750234192000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2529989"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":111,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1145\/2529989"],"URL":"https:\/\/doi.org\/10.1145\/2529989","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]},"assertion":[{"value":"2011-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-09-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-01-01","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}