{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T07:11:55Z","timestamp":1761808315015},"reference-count":130,"publisher":"Cambridge University Press (CUP)","license":[{"start":{"date-parts":[[2019,6,14]],"date-time":"2019-06-14T00:00:00Z","timestamp":1560470400000},"content-version":"unspecified","delay-in-days":44,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Numerica"],"published-print":{"date-parts":[[2019,5,1]]},"abstract":"<jats:p>We survey recent work on approximation algorithms for computing degree-constrained subgraphs in graphs and their applications in combinatorial scientific computing. The problems we consider include maximization versions of cardinality matching, edge-weighted matching, vertex-weighted matching and edge-weighted<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0962492919000035_inline1\" \/><jats:tex-math>$b$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-matching, and minimization versions of weighted edge cover and<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0962492919000035_inline2\" \/><jats:tex-math>$b$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-edge cover. Exact algorithms for these problems are impractical for massive graphs with several millions of edges. For each problem we discuss theoretical foundations, the design of several linear or near-linear time approximation algorithms, their implementations on serial and parallel computers, and applications. Our focus is on practical algorithms that yield good performance on modern computer architectures with multiple threads and interconnected processors. We also include information about the software available for these problems.<\/jats:p>","DOI":"10.1017\/s0962492919000035","type":"journal-article","created":{"date-parts":[[2019,6,13]],"date-time":"2019-06-13T11:20:43Z","timestamp":1560424843000},"page":"541-633","source":"Crossref","is-referenced-by-count":15,"title":["Approximation algorithms in combinatorial scientific computing"],"prefix":"10.1017","volume":"28","author":[{"given":"Alex","family":"Pothen","sequence":"first","affiliation":[]},{"given":"S. M.","family":"Ferdous","sequence":"additional","affiliation":[]},{"given":"Fredrik","family":"Manne","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2019,6,14]]},"reference":[{"key":"S0962492919000035_r38","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479899358443"},{"key":"S0962492919000035_r14","first-page":"23","volume-title":"Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u00a0\u201911)","author":"Blelloch","year":"2011"},{"key":"S0962492919000035_r124","doi-asserted-by":"publisher","DOI":"10.1109\/90.958329"},{"key":"S0962492919000035_r21","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"S0962492919000035_r40","doi-asserted-by":"publisher","DOI":"10.1145\/2049673.2049677"},{"key":"S0962492919000035_r90","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974690.ch10"},{"key":"S0962492919000035_r72","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1981.21"},{"key":"S0962492919000035_r118","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0066196"},{"key":"S0962492919000035_r83","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-009-0002-8"},{"key":"S0962492919000035_r24","doi-asserted-by":"publisher","DOI":"10.1145\/5925.5932"},{"key":"S0962492919000035_r28","doi-asserted-by":"publisher","DOI":"10.1007\/BF02240072"},{"key":"S0962492919000035_r6","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2016.2546258"},{"key":"S0962492919000035_r56","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584376"},{"key":"S0962492919000035_r128","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"Williamson","year":"2011"},{"key":"S0962492919000035_r65","first-page":"361","volume-title":"Proc. 14th International Conference on Artificial Intelligence and Statistics (AISTATS)","author":"Huang","year":"2011"},{"key":"S0962492919000035_r101","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.7.3.298"},{"key":"S0962492919000035_r1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.1335"},{"key":"S0962492919000035_r68","first-page":"679","volume-title":"Proceedings of the 17th European Conference on Machine Learning (ECML 2006)","author":"Jebara","year":"2006"},{"key":"S0962492919000035_r103","doi-asserted-by":"publisher","DOI":"10.1145\/195613.195663"},{"key":"S0962492919000035_r55","first-page":"144","volume-title":"Approximation Algorithms for NP-hard Problems","author":"Goemans","year":"1997"},{"key":"S0962492919000035_r13","first-page":"308","volume-title":"Proceedings of the 24th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u00a0\u201912)","author":"Blelloch","year":"2012"},{"key":"S0962492919000035_r97","doi-asserted-by":"publisher","DOI":"10.1561\/0400000057"},{"key":"S0962492919000035_r87","volume-title":"Matching Theory","author":"Lov\u00e1sz","year":"2009"},{"key":"S0962492919000035_r60","doi-asserted-by":"publisher","DOI":"10.1145\/261342.571216"},{"key":"S0962492919000035_r100","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1980.12"},{"key":"S0962492919000035_r70","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2011.606575"},{"key":"S0962492919000035_r35","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-1701-9"},{"key":"S0962492919000035_r9","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-005-1254-y"},{"key":"S0962492919000035_r26","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"S0962492919000035_r58","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(86)90016-8"},{"key":"S0962492919000035_r16","first-page":"227","volume-title":"Proceedings of the Companion Publication of the 23rd International Conference on World Wide Web","author":"Boldi","year":"2014"},{"key":"S0962492919000035_r61","doi-asserted-by":"publisher","DOI":"10.1002\/nla.1978"},{"key":"S0962492919000035_r57","doi-asserted-by":"publisher","DOI":"10.1177\/1094342012452893"},{"key":"S0962492919000035_r121","doi-asserted-by":"crossref","first-page":"343","DOI":"10.2140\/pjm.1967.21.343","article-title":"Concerning nonnegative matrices and doubly stochastic matrices","volume":"21","author":"Sinkhorn","year":"1967","journal-title":"Pacific J. Math."},{"key":"S0962492919000035_r25","volume-title":"Introduction to Algorithms","author":"Cormen","year":"2009"},{"key":"S0962492919000035_r64","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-76796-1_9"},{"key":"S0962492919000035_r53","doi-asserted-by":"publisher","DOI":"10.1137\/0710032"},{"key":"S0962492919000035_r76","volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis (SC\u00a0\u201918)","author":"Khan","year":"2018a"},{"key":"S0962492919000035_r43","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30397-5_10"},{"key":"S0962492919000035_r122","doi-asserted-by":"crossref","first-page":"454","DOI":"10.1007\/3-540-13345-3_42","volume-title":"Proceedings of the 11th Colloquium on Automata, Languages, and Programming (ICALP)","author":"Spencer","year":"1984"},{"key":"S0962492919000035_r44","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1587"},{"key":"S0962492919000035_r120","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"Schrijver","year":"2003"},{"key":"S0962492919000035_r86","doi-asserted-by":"publisher","DOI":"10.1145\/779359.779361"},{"key":"S0962492919000035_r54","doi-asserted-by":"publisher","DOI":"10.3390\/a6040824"},{"key":"S0962492919000035_r123","doi-asserted-by":"crossref","DOI":"10.2200\/S00590ED1V01Y201408AIM029","volume-title":"Graph-Based Semi-Supervised Learning","author":"Subramanya","year":"2014"},{"key":"S0962492919000035_r63","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"S0962492919000035_r126","unstructured":"Tangwongsan, K. (2011), Efficient parallel approximation algorithms. PhD thesis, Carnegie Mellon University, Pittsburgh, PA."},{"key":"S0962492919000035_r17","doi-asserted-by":"publisher","DOI":"10.1177\/1094342011403516"},{"key":"S0962492919000035_r36","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.70"},{"key":"S0962492919000035_r8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15294-8_14"},{"key":"S0962492919000035_r88","doi-asserted-by":"publisher","DOI":"10.1142\/8591"},{"key":"S0962492919000035_r19","first-page":"875","volume-title":"Proceedings of the 28th Annual Symposium on Discrete Algorithms (SODA)","author":"Cao","year":"2017"},{"key":"S0962492919000035_r84","doi-asserted-by":"publisher","DOI":"10.1186\/s13326-018-0187-8"},{"key":"S0962492919000035_r42","doi-asserted-by":"publisher","DOI":"10.6028\/jres.069B.013"},{"key":"S0962492919000035_r75","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974690.ch6"},{"key":"S0962492919000035_r107","doi-asserted-by":"publisher","DOI":"10.1109\/HiPC.2015.15"},{"key":"S0962492919000035_r46","doi-asserted-by":"publisher","DOI":"10.1002\/9781118989166"},{"key":"S0962492919000035_r111","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(94)00192-8"},{"key":"S0962492919000035_r82","unstructured":"Knoblauch, V. (2007), Marriage Matching: A conjecture of Donald Knuth. Working papers 2007-15, University of Connecticut, Department of Economics."},{"key":"S0962492919000035_r77","volume-title":"Proceedings of the International Conference on High Performance Computing, Networking, Storage, and Analysis (SC\u00a0\u201912)","author":"Khan","year":"2012"},{"key":"S0962492919000035_r49","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1962.11989827"},{"key":"S0962492919000035_r15","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"S0962492919000035_r125","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581725"},{"key":"S0962492919000035_r92","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72845-0_19"},{"key":"S0962492919000035_r109","doi-asserted-by":"publisher","DOI":"10.1201\/b11644"},{"key":"S0962492919000035_r110","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1959-0106853-5"},{"key":"S0962492919000035_r79","first-page":"773","volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis (SC\u00a0\u201916)","author":"Khan","year":"2016a"},{"key":"S0962492919000035_r59","unstructured":"Hanke, S. \u00a0and Hougardy, S. (2010), New approximation algorithms for the weighted matching problem. Research report 101010, Research Institute for Discrete Mathematics, University of Bonn."},{"key":"S0962492919000035_r130","doi-asserted-by":"publisher","DOI":"10.1137\/0602010"},{"key":"S0962492919000035_r93","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592052"},{"key":"S0962492919000035_r95","first-page":"486","article-title":"The stable marriage problem","volume":"14","author":"McVitie","year":"1971","journal-title":"Commun. Assoc. Comput. Mach."},{"key":"S0962492919000035_r74","first-page":"1","volume-title":"Advanced Simulation and Verification of Electronic and Biological Systems","author":"Keiter","year":"2011"},{"key":"S0962492919000035_r78","first-page":"22","volume-title":"2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS)","author":"Khan","year":"2018b"},{"key":"S0962492919000035_r69","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1145\/1553374.1553432","volume-title":"Proceedings of the 26th Annual International Conference on Machine Learning (ICML\u00a0\u201909)","author":"Jebara","year":"2009"},{"key":"S0962492919000035_r2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8369-7_2"},{"key":"S0962492919000035_r11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40047-6_66"},{"key":"S0962492919000035_r127","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04565-7"},{"key":"S0962492919000035_r80","doi-asserted-by":"publisher","DOI":"10.1137\/15M1026304"},{"key":"S0962492919000035_r91","doi-asserted-by":"publisher","DOI":"10.14778\/2536360.2536362"},{"key":"S0962492919000035_r81","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1036"},{"key":"S0962492919000035_r62","doi-asserted-by":"publisher","DOI":"10.1145\/2513109.2513113"},{"key":"S0962492919000035_r85","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-011-0127-7"},{"key":"S0962492919000035_r119","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366855"},{"key":"S0962492919000035_r39","doi-asserted-by":"publisher","DOI":"10.1201\/b11644-3"},{"key":"S0962492919000035_r18","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898717754"},{"key":"S0962492919000035_r102","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0006528"},{"key":"S0962492919000035_r10","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(94)90237-2"},{"key":"S0962492919000035_r23","doi-asserted-by":"publisher","DOI":"10.1137\/0608045"},{"key":"S0962492919000035_r5","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2016.103"},{"key":"S0962492919000035_r20","first-page":"3192","volume-title":"Advances in Neural Information Processing Systems (NIPS 2013)","author":"Choromanski","year":"2013"},{"key":"S0962492919000035_r98","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1958-027-8"},{"key":"S0962492919000035_r31","doi-asserted-by":"publisher","DOI":"10.1137\/17M1140029"},{"key":"S0962492919000035_r37","doi-asserted-by":"publisher","DOI":"10.1145\/2529989"},{"key":"S0962492919000035_r66","unstructured":"Huang, D. \u00a0and Pettie, S. (2017), Approximate generalized matching: $f$ -factors and $f$ -edge covers. arXiv:1706.05761"},{"key":"S0962492919000035_r129","doi-asserted-by":"publisher","DOI":"10.1007\/BF01932966"},{"key":"S0962492919000035_r105","volume-title":"Proceedings of the Cray User\u2019s Group Meeting (CUG), 2010","author":"Murphy","year":"2010"},{"key":"S0962492919000035_r71","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139519793.013"},{"key":"S0962492919000035_r99","first-page":"528","volume-title":"Algorithms: 14th Annual European Symposium on Algorithms (ESA 2006)","author":"Mestre","year":"2006"},{"key":"S0962492919000035_r73","first-page":"352","volume-title":"Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC\u00a0\u201990)","author":"Karp","year":"1990"},{"key":"S0962492919000035_r3","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2019.09.013"},{"key":"S0962492919000035_r104","doi-asserted-by":"publisher","DOI":"10.1145\/351827.384250"},{"key":"S0962492919000035_r30","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2011.06.003"},{"key":"S0962492919000035_r116","doi-asserted-by":"publisher","DOI":"10.1145\/98267.98287"},{"key":"S0962492919000035_r34","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1145\/1077464.1077472","article-title":"A linear time approximation algorithm for weighted matchings in graphs","volume":"1","author":"Drake","year":"2005","journal-title":"ACM Trans. Algorithms"},{"key":"S0962492919000035_r96","unstructured":"Mehlhorn, K. \u00a0and N\u00e4her, S. (1999), LEDA: A platform for combinatorial and geometric computing. www.algorithmic-solutions.com\/leda\/index.htm"},{"key":"S0962492919000035_r108","doi-asserted-by":"crossref","first-page":"1067","DOI":"10.1137\/S0097539798336073","article-title":"A polynomial approximation for the minimum fill-in problem","volume":"30","author":"Natanzon","year":"2000","journal-title":"SIAM J. Comput."},{"key":"S0962492919000035_r106","first-page":"637","volume-title":"Proceedings of the International Parallel and Distributed Processing Symposium Workshops (IPDPS)","author":"Naim","year":"2018"},{"key":"S0962492919000035_r33","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00393-9"},{"key":"S0962492919000035_r50","first-page":"133","article-title":"\u00dcber extreme Punkt- und Kantenmengen","volume":"2","author":"Gallai","year":"1959","journal-title":"Annales Universitatis Scientiarum Budapestinensis de Rolando E\u00f6tv\u00f6s Nominatae, Sectio Mathematica"},{"key":"S0962492919000035_r115","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(93)90121-4"},{"key":"S0962492919000035_r45","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975215.10"},{"key":"S0962492919000035_r51","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144504444711"},{"key":"S0962492919000035_r32","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44867-5_9"},{"key":"S0962492919000035_r52","doi-asserted-by":"publisher","DOI":"10.1137\/050639879"},{"key":"S0962492919000035_r117","first-page":"259","volume-title":"1999 Proceedings of 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u00a099)","author":"Preis","year":"1999,"},{"key":"S0962492919000035_r114","first-page":"122","article-title":"Combinatorial algorithms for computing column space bases that have sparse inverses","volume":"22","author":"Pinar","year":"2006","journal-title":"Electron. Trans. Numer. Anal."},{"key":"S0962492919000035_r48","doi-asserted-by":"publisher","DOI":"10.1145\/3183369"},{"key":"S0962492919000035_r67","volume-title":"Norsk Informatikkonferanse 2014","author":"Idelberger","year":"2014"},{"key":"S0962492919000035_r112","doi-asserted-by":"publisher","DOI":"10.1287\/moor.7.1.67"},{"key":"S0962492919000035_r4","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90178-5"},{"key":"S0962492919000035_r113","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.05.007"},{"key":"S0962492919000035_r29","first-page":"850","volume-title":"Proceedings of 19th International Euro-Par Conference on Parallel Processing","author":"Deveci","year":"2013"},{"key":"S0962492919000035_r12","doi-asserted-by":"publisher","DOI":"10.1145\/1360443.1360462"},{"key":"S0962492919000035_r27","doi-asserted-by":"publisher","DOI":"10.14778\/1988776.1988782"},{"key":"S0962492919000035_r7","article-title":"A distributed memory approximation algorithm for maximum weight perfect bipartite matching","author":"Azad","year":"2018","journal-title":"SIAM J. Sci. Comput."},{"key":"S0962492919000035_r94","doi-asserted-by":"publisher","DOI":"10.1007\/BF01874388"},{"key":"S0962492919000035_r22","unstructured":"Cohen, J. \u00a0and Castonguay, P. (2012), Efficient graph matching and coloring on GPUs. Presentation available at: http:\/\/on-demand.gputechconf.com\/gtc\/2012\/presentations\/S0332-Efficient-Graph-Matching-and-Coloring-on-GPUs.pdf"},{"key":"S0962492919000035_r47","first-page":"448","volume-title":"Proceedings of the 15th Annual ACM Symposium on the Theory of Computing (STOC\u00a0\u201983)","author":"Gabow","year":"1983"},{"key":"S0962492919000035_r41","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2015.06.009"},{"key":"S0962492919000035_r89","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.61"}],"container-title":["Acta Numerica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0962492919000035","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,17]],"date-time":"2023-09-17T12:08:09Z","timestamp":1694952489000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0962492919000035\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,1]]},"references-count":130,"alternative-id":["S0962492919000035"],"URL":"https:\/\/doi.org\/10.1017\/s0962492919000035","relation":{},"ISSN":["0962-4929","1474-0508"],"issn-type":[{"value":"0962-4929","type":"print"},{"value":"1474-0508","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,1]]}}}