Approximation algorithms in combinatorial scientific computing.

*(English)*Zbl 1440.68337This paper conducts a thorough survey on approximation algorithms for two classical optimization problems on graphs: matching and edge cover. The problems involve the computation of degree-constrained subgraphs of a graph that might represent its significant subgraphs in order to reduce the computational costs and memory required of algorithms that obtain some useful information from the graph.

A matching is a subset of vertex-disjoint edges and we either seek to maximize the cardinality of a matching or, when weights are assigned to edges, maximize the sum of the weights of edges in a matching. The authors also discuss a less-studied variant where the weights are on the vertices instead of the edges. A generalization of matching is the \(b\)-matching problem, where we are given natural numbers \(b(v)\) for each vertex \(v\) in the graph and are required to choose at most \(b(v)\) matched edges incident on \(v\).

The edge cover problem requires to choose at least one edge incident on each vertex to belong to the edge cover. Here we seek to minimize the cardinality of the edges in the cover or the sum of weights of the edges in the cover. The generalization of edge cover leads to the \(b\)-edge cover problem where, given natural numbers \(b(v)\) for each vertex \(v\), we are required to choose at least \(b(v)\) edges incident on \(v\) to belong to the edge cover.

Exact algorithms for both problems and their variants have polynomial time complexity with the asymptotic run-time larger than the product of the number of edges times the square root of the number of vertices, and they also have a little concurrency. In order to make them practical for graphs with billions of vertices and edges, the paper also focuses on approximation algorithms with either near-linear time complexity in the size of the graph or algorithms that possess high concurrency so that they can be implemented efficiently on parallel computers.

The paper also includes a comprehensive comparison of various implementations of approximation algorithms.

A matching is a subset of vertex-disjoint edges and we either seek to maximize the cardinality of a matching or, when weights are assigned to edges, maximize the sum of the weights of edges in a matching. The authors also discuss a less-studied variant where the weights are on the vertices instead of the edges. A generalization of matching is the \(b\)-matching problem, where we are given natural numbers \(b(v)\) for each vertex \(v\) in the graph and are required to choose at most \(b(v)\) matched edges incident on \(v\).

The edge cover problem requires to choose at least one edge incident on each vertex to belong to the edge cover. Here we seek to minimize the cardinality of the edges in the cover or the sum of weights of the edges in the cover. The generalization of edge cover leads to the \(b\)-edge cover problem where, given natural numbers \(b(v)\) for each vertex \(v\), we are required to choose at least \(b(v)\) edges incident on \(v\) to belong to the edge cover.

Exact algorithms for both problems and their variants have polynomial time complexity with the asymptotic run-time larger than the product of the number of edges times the square root of the number of vertices, and they also have a little concurrency. In order to make them practical for graphs with billions of vertices and edges, the paper also focuses on approximation algorithms with either near-linear time complexity in the size of the graph or algorithms that possess high concurrency so that they can be implemented efficiently on parallel computers.

The paper also includes a comprehensive comparison of various implementations of approximation algorithms.

Reviewer: Vladimír Lacko (Košice)

##### MSC:

68W25 | Approximation algorithms |

05C07 | Vertex degrees |

05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |

05C85 | Graph algorithms (graph-theoretic aspects) |

68R10 | Graph theory (including graph drawing) in computer science |

68W10 | Parallel algorithms in computer science |

68W40 | Analysis of algorithms |

90C27 | Combinatorial optimization |

##### Keywords:

approximation algorithms; degree-constrained subgraphs; combinatorial optimization; cardinality matching; edge-weighted matching; vertex-weighted matching; edge-weighted \(b\)-matching, weighted edge cover; \(b\)-edge cover
Full Text:
DOI

##### References:

[1] | Achlioptas, D. and Naor, A. (2005), ‘The two possible values of the chromatic number of a random graph’, Ann. of Math.162, 1335-1351. · Zbl 1094.05048 |

[2] | Agrawal, A., Klein, P. N. and Ravi, R. (1993), Cutting down on fill using nested dissection: Provably good elimination orderings. In Graph Theory and Sparse Matrix Computations (George, A., Gilbert, J. R. and Liu, J. W. H., eds), Springer, pp. 31-55. · Zbl 0803.68082 |

[3] | Al-Herz, A. and Pothen, A. (2019), ‘A \(2/3\)-approximation algorithm for vertex-weighted matching’, Discrete Appl. Math., under review. arXiv:1902.05877 · Zbl 07025127 |

[4] | Anstee, R. P., A polynomial algorithm for \(b\)-matchings: An alternative approach, Inform. Process. Lett., 24, 153-157, (1987) · Zbl 0655.90090 |

[5] | Azad, A. and Buluç, A. (2016), Distributed memory algorithms for maximum cardinality matching on bipartite graphs. In 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS), IEEE, pp. 32-42. |

[6] | Azad, A., Buluç, A. and Pothen, A. (2017), ‘Computing maximum cardinality matchings in parallel on bipartite graphs via tree grafting’, IEEE Trans. Parallel Distrib. Syst.28, 44-59. |

[7] | Azad, A., Buluç, A., Li, X. S., Wang, X. and Langguth, J. (2018), ‘A distributed memory approximation algorithm for maximum weight perfect bipartite matching’, SIAM J. Sci. Comput., under review. arXiv:1801.09809v1 |

[8] | Azad, A., Langguth, J., Fang, Y., Qi, A. and Pothen, A. (2010), Identifying rare cell populations in comparative flow cytometry. In Algorithms in Bioinformatics: International Workshop on Algorithms in Bioinformatics (WABI), , Springer, pp. 162-175. |

[9] | Bast, H., Mehlhorn, K., Schäfer, G. and Tamaki, H. (2006), ‘Matching algorithms are fast in sparse random graphs’, Theory Comput. Syst.39, 3-14. · Zbl 1104.68078 |

[10] | Bell, C. E., Weighted matching with vertex weights: An application to scheduling training sessions in NASA space shuttle cockpit simulators, Europ. J. Oper. Res., 73, 443-449, (1994) · Zbl 0806.90076 |

[11] | Birn, M., Osipov, V., Sanders, P., Schulz, C. and Sitchinava, N. (2013), Efficient parallel and external matching. In Euro-Par 2013 Parallel Processing, , Springer, pp. 659-670. |

[12] | Birnbaum, B. and Mathieu, C. (2008), ‘On-line bipartite matching made simple’, ACM SIGACT News39, 80-87. |

[13] | Blelloch, G. E., Fineman, J. T. and Shun, J. (2012), Greedy sequential maximal independent set and matching are parallel on average. In Proceedings of the 24th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’12), ACM, pp. 308-317. |

[14] | Blelloch, G. E., Peng, R. and Tangwongsan, K. (2011), Linear work parallel greedy approximate set cover and variants. In Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’11), ACM, pp. 23-32. |

[15] | Boldi, P. and Vigna, S. (2004), The WebGraph framework I: Compression techniques. In Proceedings of the 13th International Conference on World Wide Web (WWW 2004), ACM, pp. 595-601. |

[16] | Boldi, P., Marino, A., Santini, M. and Vigna, S. (2014), BUbiNG: Massive crawling for the masses. In Proceedings of the Companion Publication of the 23rd International Conference on World Wide Web, ACM, pp. 227-228. |

[17] | Buluç, A. and Gilbert, J. R. (2011), ‘The Combinatorial BLAS: Design, implementation and applications’, Internat. J. High Perf. Comput. Appl.25, 496-509. |

[18] | Burkard, R., Dell’Amico, M. and Martello, S. (2009), Assignment Problems, SIAM. · Zbl 1196.90002 |

[19] | Cao, Y. and Sandeep, R. B. (2017), Minimum fill-in: Inapproximability and almost tight lower bounds. In Proceedings of the 28th Annual Symposium on Discrete Algorithms (SODA), SIAM, pp. 875-880. · Zbl 1410.68141 |

[20] | Choromanski, K. M., Jebara, T. and Tang, K. (2013), Adaptive anonymity via b-matching. In Advances in Neural Information Processing Systems (NIPS 2013) (Burges, C. J. C.et al., eds), pp. 3192-3200. |

[21] | Chvatal, V., A greedy heuristic for the set-covering problem, Math. Oper. Res., 4, 233-235, (1979) · Zbl 0443.90066 |

[22] | Cohen, J. and 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 |

[23] | Coleman, T. F. and Pothen, A. (1987), ‘The null space problem II: Algorithms’, SIAM J. Algebraic Discrete Methods8, 544-563. |

[24] | Coleman, T. F., Edenbrandt, A. and Gilbert, J. R. (1986), ‘Predicting fill for sparse orthogonal factorization’, J. Assoc. Comput. Mach.33, 517-532. · Zbl 0635.65036 |

[25] | Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2009), Introduction to Algorithms, MIT Press. · Zbl 1187.68679 |

[26] | Davis, T. and Hu, Y. (2011), ‘The University of Florida Sparse Matrix Collection’, ACM Trans. Math. Softw.38, 1:1-1:25. · Zbl 1365.65123 |

[27] | De Francisci Morales, G., Gionis, A. and Sozio, M. (2011), ‘Social content matching in MapReduce’, Proc. VLDB Endowment4, 460-469. |

[28] | Derigs, U. and Metz, A. (1986), ‘On the use of optimal fractional matchings for solving the (integer) matching problem’, Computing36, 263-270. · Zbl 0582.65051 |

[29] | Deveci, M., Kaya, K., Uçar, B. and Çatalyürek, Ü. (2013), GPU accelerated maximum cardinality matching algorithms for bipartite graphs. In Proceedings of 19th International Euro-Par Conference on Parallel Processing, pp. 850-861. |

[30] | Dezső, B., Jüttner, A. and Kovács, P. (2011), ‘LEMON: An open source C++ graph template library’, Electron. Notes Theoret. Comput. Sci.264, 23-45. |

[31] | Dobrian, F., Halappanavar, M., Pothen, A. and Al-Herz, A. (2019), ‘A \(2/3\)-approximation algorithm for vertex-weighted matching in bipartite graphs’, SIAM J. Sci. Comput.41, A566-A591. · Zbl 07025127 |

[32] | Drake, D. and Hougardy, S. (2003a), Linear time local improvements for weighted matchings in graphs. In Experimental and Efficient Algorithms, (Jansen, K., Margraf, M., Mastrolilli, M. and Rolim, J., eds), , Springer, pp. 107-119. · Zbl 1023.68880 |

[33] | Drake, D. E. and Hougardy, S. (2003b), ‘A simple approximation algorithm for the weighted matching problem’, Inform. Process. Lett.85, 211-213. · Zbl 1173.68861 |

[34] | Drake, D. E. and Hougardy, S. (2005), ‘A linear time approximation algorithm for weighted matchings in graphs’, ACM Trans. Algorithms1, 107-122. · Zbl 1321.05279 |

[35] | Du, D., Ko, K. and Hu, X. (2012), Design and Analysis of Approximation Algorithms, Springer. · Zbl 1237.68009 |

[36] | Duan, R. and Pettie, S. (2010), Approximating maximum weight matching in near-linear time. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS ’10), IEEE, pp. 673-682. |

[37] | Duan, R. and Pettie, S. (2014), ‘Linear-time approximation for maximum weight matching’, J. Assoc. Comput. Mach.61, 1-23. · Zbl 1295.68213 |

[38] | Duff, I. S. and Koster, J. (2001), ‘On algorithms for permuting large entries to the diagonal of a sparse matrix’, SIAM J. Matrix Anal. Appl.22, 973-996. · Zbl 0979.05087 |

[39] | Duff, I. S. and Uçar, B. (2012), Combinatorial problems in solving linear systems. In Combinatorial Scientific Computing (Naumann, U. and Schenk, O., eds), CRC, pp. 21-68. |

[40] | Duff, I. S., Kaya, K. and Uçar, B. (2011), ‘Design, implementation, and analysis of maximum transversal algorithms’, ACM Trans. Math. Softw.38, 13:1-13:31. |

[41] | Dufossé, F., Kaya, K. and Uçar, B. (2015), ‘Two approximation algorithms for bipartite matching on multicore architectures’, J. Parallel Distrib. Comput.85, 62-78. |

[42] | Edmonds, J., Maximum matching and a polyhedron with 0, 1-vertices, J. Res. Nat. Bureau Standards, 69B, 125-130, (1965) · Zbl 0141.21802 |

[43] | Fagginger Auer, B. O. and Bisseling, R. H. (2012), A GPU algorithm for greedy graph matching. In Facing the Multicore-Challenge II (Keller, R., Kramer, D. and Weiss, J., eds), Springer, pp. 108-119. |

[44] | Feige, U. and Kilian, J. (1998), ‘Zero knowledge and the chromatic number’, J. Comput. Systems Sci.57, 187-199. · Zbl 0921.68089 |

[45] | Ferdous, S., Pothen, A. and Khan, A. (2018), New approximation algorithms for minimum weighted edge cover. In 2018 Proceedings of the Seventh SIAM Workshop on Combinatorial Scientific Computing, SIAM, pp. 97-108. |

[46] | Fritzson, P., Principles of Object-Oriented Modeling and Simulation with Modelica 3.3: A Cyber-Physical Approach, (2014), Wiley/IEEE |

[47] | Gabow, H. N. (1983), An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In Proceedings of the 15th Annual ACM Symposium on the Theory of Computing (STOC ’83), ACM, pp. 448-456. |

[48] | Gabow, H. N. (2018), ‘Data structures for weighted matching and extensions to \(b\)-matching and \(f\)-factors’, ACM Trans. Algorithms14, 39:1-39:80. · Zbl 06979229 |

[49] | Gale, D. and Shapley, L. S. (1962), ‘College admissions and the stability of marriage’, Amer. Math. Monthly69, 9-15. · Zbl 0109.24403 |

[50] | Gallai, T., Über extreme Punkt- und Kantenmengen, Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae, Sectio Mathematica, 2, 133-138, (1959) · Zbl 0094.36105 |

[51] | Gebremedhin, A. H., Manne, F. and Pothen, A. (2005), ‘What color is your Jacobian? Graph coloring for computing derivatives’, SIAM Review47, 629-705. · Zbl 1076.05034 |

[52] | Gebremedhin, A. H., Tarafdar, A., Manne, F. and Pothen, A. (2007), ‘New acyclic and star coloring algorithms with application to computing Hessians’, SIAM J. Sci. Comput.29, 1042-1072. · Zbl 1140.05304 |

[53] | George, A., Nested dissection of a finite element mesh, SIAM J. Numer. Anal., 10, 345-363, (1973) · Zbl 0259.65087 |

[54] | Georgiadis, G. and Papatriantafilou, M. (2013), ‘Overlays with preferences: Distributed, adaptive approximation algorithms for matching with preference lists’, Algorithms6, 824-856. · Zbl 07042190 |

[55] | Goemans, M. X. and Williamson, D. P. (1997), The primal – dual method for approximation algorithms and its application to network design problems. In Approximation Algorithms for NP-hard Problems (Hochbaum, D. S., ed.), PWS Publishing Co., pp. 144-191. |

[56] | Grötschel, M. and Holland, O. (1985), ‘Solving matching problems with linear programming’, Math. Program.33, 243-259. |

[57] | Halappanavar, M., Feo, J., Villa, O., Dobrian, F. and Pothen, A. (2012), ‘Approximate weighted matching on emerging manycore and multithreaded architectures’, Internat. J. High Perf. Comput. Appl.26, 413-430. |

[58] | Hall, N. G. and Hochbaum, D. S. (1986), ‘A fast approximation algorithm for the multicovering problem’, Discrete Appl. Math.15, 35-40. · Zbl 0602.90110 |

[59] | Hanke, S. and Hougardy, S. (2010), New approximation algorithms for the weighted matching problem. Research report 101010, Research Institute for Discrete Mathematics, University of Bonn. |

[60] | D. S. Hochbaum, ed. (1997), Approximation Algorithms for NP-hard Problems, PWS Publishing Co. |

[61] | Hogg, J. and Scott, J. (2015), ‘On the use of suboptimal matchings for scaling and ordering sparse symmetric matrices’, Numer. Linear Algebra Appl.22, 648-663. · Zbl 1363.65039 |

[62] | Hogg, J. and Scott, J. (2013), ‘Pivoting strategies for tough sparse indefinite systems’, ACM Trans. Math. Softw.40, 4. · Zbl 1295.65054 |

[63] | Hopcroft, J. and Karp, R. (1973), ‘An \(n^{5/2}\) algorithm for maximum matchings in bipartite graphs’, SIAM J. Comput.2, 225-231. · Zbl 0266.05114 |

[64] | Hougardy, S. (2009), Linear time approximation algorithms for degree constrained subgraph problems. In Research Trends in Combinatorial Optimization (Cook, W. J., Lovász, L. and Vygen, J., eds), Springer, pp. 185-200. · Zbl 1359.90119 |

[65] | Huang, B. C. and Jebara, T. (2011), Fast b-matching via sufficient selection belief propagation. In Proc. 14th International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 361-369. |

[66] | Huang, D. and Pettie, S. (2017), Approximate generalized matching: \(f\)-factors and \(f\)-edge covers. arXiv:1706.05761 |

[67] | Idelberger, A. and Manne, F. (2014), New iterative algorithms for weighted matching. In Norsk Informatikkonferanse 2014. www.nik.no/publikasjoner/ |

[68] | Jebara, T. and Shchogolev, V. (2006), b-matching for spectral clustering. In Proceedings of the 17th European Conference on Machine Learning (ECML 2006), , Springer, pp. 679-686. |

[69] | Jebara, T., Wang, J. and Chang, S.-F. (2009), Graph construction and b-matching for semi-supervised learning. In Proceedings of the 26th Annual International Conference on Machine Learning (ICML ’09), ACM, pp. 441-448. |

[70] | Juedes, D. and Jones, J. (2012), ‘Coloring Jacobians revisited: A new algorithm for acyclic and star bicoloring’, Optim. Methods Softw.27, 295-309. · Zbl 1253.68362 |

[71] | Kang, R. J. and Mcdiarmid, C. (2015), Colouring random graphs. In Topics in Chromatic Graph Theory (Wilson, R. J. and Beineke, L. W., eds), Cambridge University Press, pp. 199-219. · Zbl 1348.05076 |

[72] | Karp, R. M. and Sipser, M. (1981), Maximum matching in sparse random graphs. In Proceedings of the 22nd Annual Symposium on Foundations of Computer Science (SFCS 1981), pp. 364-375. |

[73] | Karp, R. M., Vazirani, U. and Vazirani, V. (1990), An optimal algorithm for on-line bipartite matching. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC ’90), ACM, pp. 352-358. |

[74] | Keiter, E. R., Thornquist, H. K., Hoekstra, R. J., Russo, T. V., Schiek, R. L. and Rankin, E. L. (2011), Parallel transistor-level circuit simulation. In Advanced Simulation and Verification of Electronic and Biological Systems (Li, P., Silveira, L. M. and Feldmann, P., eds), Springer, pp. 1-21. |

[75] | Khan, A. and Pothen, A. (2016), A new 3/2-approximation algorithm for the b-edge cover problem. In 2016 Proceedings of the Seventh SIAM Workshop on Combinatorial Scientific Computing, SIAM, pp. 52-61. |

[76] | Khan, A., Choromanski, K., Pothen, A., Ferdous, S., Halappanavar, M. and Tumeo, A. (2018a), Adaptive anonymization of data using b-edge cover. In Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis (SC ’18), IEEE, pp. 59:1-59:11. |

[77] | Khan, A. M., Gleich, D. F., Pothen, A. and Halappanavar, M. (2012), A multithreaded algorithm for network alignment via approximate matching. In Proceedings of the International Conference on High Performance Computing, Networking, Storage, and Analysis (SC ’12), IEEE, pp. 64:1-64:11. |

[78] | Khan, A., Pothen, A. and Ferdous, S. M. (2018b), Parallel algorithms through approximation: b-edge cover. In 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS), IEEE, pp. 22-33. |

[79] | Khan, A., Pothen, A., Patwary, M. M., Halappanavar, M., Satish, N., Sundaram, N. and Dubey, P. (2016a), Designing scalable b-matching algorithms on distributed memory multiprocessors by approximation. In Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis (SC ’16), IEEE, pp. 773-783. |

[80] | Khan, A., Pothen, A., Patwary, M. M., Satish, N., Sundaram, N., Manne, F., Halappanavar, M. and Dubey, P. (2016b), ‘Efficient approximation algorithms for weighted \(b\)-matching’, SIAM J. Sci. Comput.38, S593-S619. · Zbl 1386.68220 |

[81] | Khuller, S., Vishkin, U. and Young, N. (1994), ‘A primal – dual parallel approximation technique applied to weighted set and vertex covers’, J. Algorithms17, 280-289. · Zbl 0938.68946 |

[82] | Knoblauch, V. (2007), Marriage Matching: A conjecture of Donald Knuth. Working papers 2007-15, University of Connecticut, Department of Economics. |

[83] | Kolmogorov, V., BLOSSOM V: A new implementation of a minimum cost perfect matching algorithm, Math. Prog. Comput., 1, 43-67, (2009) · Zbl 1171.05429 |

[84] | Kolyvakis, P., Kalousis, A., Smith, B. and Kiritsis, D. (2018), ‘Biomedical ontology alignment: An approach based on representation learning’, J. Biomed. Semantics9, 21. |

[85] | Koufogiannakis, C. and Young, N. E. (2011), ‘Distributed algorithms for covering, packing and maximum weighted matching’, Distrib. Comput.24, 45-63. · Zbl 1231.68276 |

[86] | Li, X. S. and Demmel, J. W. (2003), ‘SuperLU_DIST: A scalable distributed-memory sparse direct solver for unsymmetric linear systems’, ACM Trans. Math. Softw.29, 110-140. · Zbl 1068.90591 |

[87] | Lovász, L. and Plummer, M. D. (2009), Matching Theory, AMS. |

[88] | Manlove, D. F., Algorithmics of Matching Under Preferences, (2013), World Scientific · Zbl 1283.68018 |

[89] | Manne, F. and Halappanavar, M. (2014), New effective multithreaded matching algorithms. In 2014 IEEE 28th International Parallel and Distributed Processing Symposium (IPDPS), IEEE, pp. 519-528. |

[90] | Manne, F., Naim, M., Lerring, H. and Halappanavar, M. (2016), On stable marriages and greedy matchings. In 2016 Proceedings of the Seventh SIAM Workshop on Combinatorial Scientific Computing, SIAM, pp. 92-101. |

[91] | Manshadi, F. M., Awerbuch, B., Gemulla, R., Khandekar, R., Mestre, J. and Sozio, M. (2013), ‘A distributed algorithm for large-scale generalized matching’, Proc. VLDB Endowment6, 613-624. |

[92] | Maue, J. and Sanders, P. (2007), Engineering algorithms for approximate weighted matching. In Experimental Algorithms: 6th International Workshop on Experimental and Efficient Algorithms (WEA 2007), , Springer, pp. 242-255. · Zbl 1203.68317 |

[93] | Mccormick, S. T., Optimal approximation of sparse Hessians and its equivalence to a graph coloring problem, Math. Program., 26, 153-171, (1983) · Zbl 0507.65027 |

[94] | Mcdiarmid, C., Colouring random graphs, Ann. Oper. Res., 1, 183-200, (1984) |

[95] | Mcvitie, D. G. and Wilson, L. B. (1971), ‘The stable marriage problem’, Commun. Assoc. Comput. Mach.14, 486-490. |

[96] | Mehlhorn, K. and Näher, S. (1999), LEDA: A platform for combinatorial and geometric computing. www.algorithmic-solutions.com/leda/index.htm · Zbl 0976.68156 |

[97] | Mehta, A., Online matching and ad allocation, Found. Trends. Theor. Comput. Sci., 8, 265-368, (2012) · Zbl 1278.68018 |

[98] | Mendelsohn, N. S. and Dulmage, A. L. (1958), ‘Some generalizations of the problem of distinct representatives’, Canad. J. Math.10, 230-241. · Zbl 0082.01803 |

[99] | Mestre, J. (2006), Greedy in approximation algorithms. In Algorithms: 14th Annual European Symposium on Algorithms (ESA 2006), , Springer, pp. 528-539. · Zbl 1131.68594 |

[100] | Micali, S. and Vazirani, V. V. (1980), An O (√|V|⋅|E|) algorithm for finding maximum matching in general graphs. In Proceedings of the 21st Annual Symposium on Foundations of Computer Science (SFCS 1980), IEEE, pp. 17-27. |

[101] | Miller, D. L. and Pekny, J. F. (1995), ‘A staged primal – dual algorithm for perfect \(b\)-matching with edge capacities’, ORSA J. Comput.7, 298-320. · Zbl 0859.90116 |

[102] | Minoux, M. (1978), Accelerated greedy algorithms for maximizing submodular set functions. In Optimization Techniques: Proceedings of the 8th IFIP Conference on Optimization Techniques (IFIP 1977) (Stoer, J., ed.), Springer, pp. 234-243. · Zbl 0372.90128 |

[103] | Motwani, R., Average-case analysis of algorithms for matchings and related problems, J. Assoc. Comput. Mach., 41, 1329-1356, (1994) · Zbl 0829.68070 |

[104] | Müller-Hannemann, M. and Schwartz, A. (2000), ‘Implementing weighted \(b\)-matching algorithms: Insights from a computational study’, J. Exp. Algorithmics5, 8. · Zbl 1071.68562 |

[105] | Murphy, R. C., Wheeler, K. B., Barrett, B. W. and Ang, J. A. (2010), Introducing the Graph 500. In Proceedings of the Cray User’s Group Meeting (CUG), 2010. |

[106] | Naim, M. and Manne, F. (2018), Scalable b-matching on GPUs. In Proceedings of the International Parallel and Distributed Processing Symposium Workshops (IPDPS), pp. 637-646. |

[107] | Naim, M., Manne, F., Halappanavar, M., Tumeo, A. and Langguth, J. (2015), Optimizing approximate weighted matching on Nvidia Kepler K40. In IEEE 22nd International Conference on High Performance Computing (HiPC 2015), pp. 105-114. |

[108] | Natanzon, A., Shamir, R. and Sharan, R. (2000), ‘A polynomial approximation for the minimum fill-in problem’, SIAM J. Comput.30, 1067-1079. · Zbl 0969.68194 |

[109] | U. Naumann and O. Schenk, eds (2012), Combinatorial Scientific Computing, CRC Press. |

[110] | Norman, R. Z. and Rabin, M. O. (1959), ‘An algorithm for a minimum cover of a graph’, Proc. Amer. Math. Soc.10, 315-319. · Zbl 0093.37702 |

[111] | Olschowka, M. and Neumaier, A. (1996), ‘A new pivoting strategy for Gaussian elimination’, Linear Algebra Appl.240(suppl. C), 131-151. · Zbl 0852.65021 |

[112] | Padberg, M. W. and Rao, M. R. (1982), ‘Odd minimum cut-sets and \(b\)-matchings’, Math. Oper. Res.7, 67-80. · Zbl 0499.90056 |

[113] | Pettie, S. and Sanders, P. (2004), ‘A simpler linear time \(2/3-𝜖\) approximation for maximum weight matching’, Inform. Process. Lett.91, 271-276. · Zbl 1178.68686 |

[114] | Pinar, A., Chow, E. and Pothen, A. (2006), ‘Combinatorial algorithms for computing column space bases that have sparse inverses’, Electron. Trans. Numer. Anal.22, 122-145. · Zbl 1112.65040 |

[115] | Pothen, A., Predicting the structure of sparse orthogonal factors, Linear Algebra Appl., 194, 183-203, (1993) · Zbl 0797.65014 |

[116] | Pothen, A. and Fan, C.-J. (1990), ‘Computing the block triangular form of a sparse matrix’, ACM Trans. Math. Softw.16, 303-324. · Zbl 0900.65117 |

[117] | Preis, R. (1999,), Linear time 1/2-approximation algorithm for maximum weighted matching in general graphs. In 1999 Proceedings of 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS 99), , Springer, pp. 259-269. · Zbl 0927.05075 |

[118] | Pulleyblank, W. R. (1973), Faces of matching polyhedra. PhD thesis, Faculty of Mathematics, University of Waterloo. |

[119] | Rajagopalan, S. and Vazirani, V. V. (1993), Primal – dual RNC approximation algorithms for (multi)-set (multi)-cover and covering integer programs. In Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science (SFCS ’93), IEEE, pp. 322-331. |

[120] | Schrijver, A., Combinatorial Optimization: Polyhedra and Efficiency, (2003), Springer · Zbl 1041.90001 |

[121] | Sinkhorn, R. and Knopp, P. (1967), ‘Concerning nonnegative matrices and doubly stochastic matrices’, Pacific J. Math.21, 343-348. · Zbl 0152.01403 |

[122] | Spencer, T. H. and Mayr, E. W. (1984), Node weighted matching. In Proceedings of the 11th Colloquium on Automata, Languages, and Programming (ICALP), , Springer, pp. 454-464. · Zbl 0566.05047 |

[123] | Subramanya, A. and Talukdar, P. P. (2014), Graph-Based Semi-Supervised Learning, , Morgan & Claypool. · Zbl 1296.68002 |

[124] | Tabatabaee, V., Georgiadis, L. and Tassiulas, L. (2001), ‘QoS provisioning and tracking fluid policies in input queueing switches’, IEEE/ACM Trans. Netw.9, 605-617. |

[125] | Tamir, A. and Mitchell, J. S. B. (1998), ‘A maximum \(b\)-matching problem arising from median location models with applications to the roommates problem’, Math. Program.80, 171-194. · Zbl 0897.90189 |

[126] | Tangwongsan, K. (2011), Efficient parallel approximation algorithms. PhD thesis, Carnegie Mellon University, Pittsburgh, PA. |

[127] | Vazirani, V. V., Approximation Algorithms, (2003), Springer · Zbl 1005.68002 |

[128] | Williamson, D. P. and Shmoys, D. B. (2011), The Design of Approximation Algorithms, Cambridge University Press. · Zbl 1219.90004 |

[129] | Wilson, L. B., An analysis of the marriage matching assignment algorithm, BIT, 12, 569-575, (1972) · Zbl 0249.05006 |

[130] | Yannakakis, M., Computing the minimum fill-in is NP-complete, SIAM J. Algebraic Discrete Methods, 2, 77-79, (1981) · Zbl 0496.68033 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.