{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,4]],"date-time":"2025-04-04T12:11:41Z","timestamp":1743768701539,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2022,2,25]],"date-time":"2022-02-25T00:00:00Z","timestamp":1645747200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,2,25]],"date-time":"2022-02-25T00:00:00Z","timestamp":1645747200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1217338","CNS-1318294"],"award-info":[{"award-number":["CCF-1217338","CNS-1318294"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100008982","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1514383","CCF-1637546"],"award-info":[{"award-number":["CCF-1514383","CCF-1637546"]}],"id":[{"id":"10.13039\/501100008982","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Science Foundation","award":["CCF-1815316"],"award-info":[{"award-number":["CCF-1815316"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,7]]},"DOI":"10.1007\/s00453-022-00949-5","type":"journal-article","created":{"date-parts":[[2022,2,25]],"date-time":"2022-02-25T07:02:42Z","timestamp":1645772562000},"page":"1952-1992","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Approximate Generalized Matching: f-Matchings and f-Edge Covers"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4496-2354","authenticated-orcid":false,"given":"Dawei","family":"Huang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seth","family":"Pettie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,2,25]]},"reference":[{"key":"949_CR1","unstructured":"Choromanski, K., Jebara, T., Tang, K.: Adaptive anonymity via $$b$$-matching. In: Advances in Neural Information Processing Systems 27: 27th Annual Conference on Neural Information Processing System, NIPS 2013, pp. 3192\u20133200 (2013)"},{"key":"949_CR2","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4, 233\u2013235 (1979)","journal-title":"Math. Oper. Res."},{"key":"949_CR3","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0020-0190(02)00393-9","volume":"85","author":"DE Drake","year":"2003","unstructured":"Drake, D.E., Hougardy, S.: A simple approximation algorithm for the weighted matching problem. Inf. Process. Lett. 85, 211\u2013213 (2003)","journal-title":"Inf. Process. Lett."},{"key":"949_CR4","doi-asserted-by":"publisher","first-page":"1:1","DOI":"10.1145\/2529989","volume":"61","author":"R Duan","year":"2014","unstructured":"Duan, R., Pettie, S.: Linear-time approximation for maximum weight matching. J. ACM 61, 1:1-1:23 (2014)","journal-title":"J. ACM"},{"key":"949_CR5","first-page":"8:1","volume":"14","author":"R Duan","year":"2018","unstructured":"Duan, R., Pettie, S., Su, H.: Scaling algorithms for weighted matching in general graphs. ACM Trans. Algor. 14, 8:1-8:35 (2018)","journal-title":"ACM Trans. Algor."},{"key":"949_CR6","doi-asserted-by":"publisher","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69B","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Maximum matching and a polyhedron with 0,1-vertices. J. Res. Natl. Bureau Stand.: Sect. B Math. Math. Phys. 69B, 125\u2013130 (1965)","journal-title":"J. Res. Natl. Bureau Stand.: Sect. B Math. Math. Phys."},{"key":"949_CR7","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees and flowers. Can. J. Math. 17, 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"key":"949_CR8","doi-asserted-by":"crossref","unstructured":"Edmonds, J., Johnson, E.L.: Matching: A well-solved class of integer linear programs. In: Combinatorial Optimization - Eureka, You Shrink!, Papers Dedicated to Jack Edmonds, 5th International Workshop, pp. 27\u201330 (2001)","DOI":"10.1007\/3-540-36478-1_3"},{"issue":"2","key":"949_CR9","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1145\/321941.321942","volume":"23","author":"HN Gabow","year":"1976","unstructured":"Gabow, H.N.: An efficient implementation of Edmonds\u2019 algorithm for maximum matching on graphs. J. ACM 23(2), 221\u2013234 (1976)","journal-title":"J. ACM"},{"key":"949_CR10","doi-asserted-by":"crossref","unstructured":"Gabow, H.N.: An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In: Proceedings of the 15th Annual ACM Symposium on Theory of Computing, STOC 1983, pp. 448\u2013456 (1983)","DOI":"10.1145\/800061.808776"},{"key":"949_CR11","first-page":"39:1","volume":"14","author":"HN Gabow","year":"2018","unstructured":"Gabow, H.N.: Data structures for weighted matching and extensions to $$b$$-matching and $$f$$-factors. ACM Trans. Algor. 14, 39:1-39:80 (2018)","journal-title":"ACM Trans. Algor."},{"key":"949_CR12","doi-asserted-by":"crossref","unstructured":"Gabow, H.N., Sankowski, P.: Algebraic algorithms for $$b$$-matching, shortest undirected paths, and $$f$$-factors. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 137\u2013146 (2013)","DOI":"10.1109\/FOCS.2013.23"},{"key":"949_CR13","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"HN Gabow","year":"1985","unstructured":"Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. J. Comput. Syst. Sci. 30, 209\u2013221 (1985)","journal-title":"J. Comput. Syst. Sci."},{"key":"949_CR14","doi-asserted-by":"publisher","first-page":"1013","DOI":"10.1137\/0218069","volume":"18","author":"HN Gabow","year":"1989","unstructured":"Gabow, H.N., Tarjan, R.E.: Faster scaling algorithms for network problems. SIAM J. Comput. 18, 1013\u20131036 (1989)","journal-title":"SIAM J. Comput."},{"key":"949_CR15","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1145\/115234.115366","volume":"38","author":"HN Gabow","year":"1991","unstructured":"Gabow, H.N., Tarjan, R.E.: Faster scaling algorithms for general graph-matching problems. J. ACM 38, 815\u2013853 (1991)","journal-title":"J. ACM"},{"issue":"1","key":"949_CR16","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within $$n^{1-\\epsilon }$$. Acta Math. 182(1), 105\u2013142 (1999)","journal-title":"Acta Math."},{"key":"949_CR17","doi-asserted-by":"crossref","unstructured":"Khan, A., Choromanski, K., Pothen, A., Ferdous, S.M., Halappanavar, M., Tumeo, A.: Adaptive anonymization of data using $$b$$-edge cover. In: Proceedings of the International Conference for High Performance Computing,Networking, Storage, and Analysis, SC, pp. 59:1\u201359:11 (2018)","DOI":"10.1109\/SC.2018.00062"},{"key":"949_CR18","doi-asserted-by":"crossref","unstructured":"Khan, A.M., Pothen, A.: A new $$3\/2$$-approximation algorithm for the $$b$$-edge cover problem. In: 2016 Proceedings of the Seventh SIAM Workshop on Combinatorial Scientific Computing, CSC, pp. 52\u201361 (2016)","DOI":"10.1137\/1.9781611974690.ch6"},{"key":"949_CR19","unstructured":"Lawler, E.: Combinatorial Optimization: Networks and Matroids. Dover Books on Mathematics Series (2001)"},{"key":"949_CR20","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.V.: An $$O(\\sqrt{|V|}|E|)$$ algorithm for finding maximum matching in general graphs. In: 21st Annual Symposium on Foundations of Computer Science, FOCS, pp. 17\u201327 (1980)","DOI":"10.1109\/SFCS.1980.12"},{"key":"949_CR21","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/j.ipl.2004.05.007","volume":"91","author":"S Pettie","year":"2004","unstructured":"Pettie, S., Sanders, P.: A simpler linear time $$2\/3-\\epsilon $$ approximation for maximum weight matching. Inf. Process. Lett. 91, 271\u2013276 (2004)","journal-title":"Inf. Process. Lett."},{"key":"949_CR22","unstructured":"Pulleyblank, W.: Faces of matching polyhedra. PhD thesis, University of Waterloo, Ontario, Canada (1973)"},{"key":"949_CR23","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Algorithms and Combinatorics (2002)"},{"key":"949_CR24","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"RE Tarjan","year":"1975","unstructured":"Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. J. ACM 22, 215\u2013225 (1975)","journal-title":"J. ACM"},{"key":"949_CR25","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1112\/jlms\/s1-36.1.221","volume":"s1\u201336","author":"WT Tutte","year":"1961","unstructured":"Tutte, W.T.: On the problem of decomposing a graph into $$n$$ connected factors. J. Lond. Math. Soc. s1\u201336, 221\u2013230 (1961)","journal-title":"J. Lond. Math. Soc."},{"issue":"1","key":"949_CR26","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF01305952","volume":"14","author":"VV Vazirani","year":"1994","unstructured":"Vazirani, V.V.: A theory of alternating paths and blossoms for proving correctness of the $$O(\\sqrt{|V|}|E|)$$ general graph maximum matching algorithm. Combinatorica 14(1), 71\u2013109 (1994)","journal-title":"Combinatorica"},{"key":"949_CR27","unstructured":"Vazirani, V.V.: An improved definition of blossoms and a simpler proof of the MV matching algorithm. CoRR, arXiv:1210.4594, (2012)"},{"issue":"1","key":"949_CR28","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3(1), 103\u2013128 (2007)","journal-title":"Theory Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00949-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00949-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00949-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,23]],"date-time":"2022-06-23T11:05:29Z","timestamp":1655982329000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00949-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,25]]},"references-count":28,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["949"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00949-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,2,25]]},"assertion":[{"value":"11 May 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 January 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 February 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}