Heuristic Approach to Improve the Efficiency of Maximum Weight Matching Algorithm Using Clustering

1. Hitchcock, F.L.: The distribution of a product from several sources to numerous localities. J. Math. Phys. 20(1–4), 224–230 (1941)

   Article  MathSciNet  Google Scholar 

2. Thorndike, R.L.: The problem of classification of personnel. Psychometrika 15(3), 215–235 (1950)

   Article  Google Scholar 

3. Chan, P., Huang, X., Liu, Z., Zhang, C., Zhang, S.: Assignment and pricing in roommate market. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 30 (2016)

   Google Scholar 

4. Irving, R.W.: An efficient algorithm for the ‘stable roommates’ problem. J. Algor. 6(4), 577–595 (1985)

   Article  MathSciNet  Google Scholar 

5. Zhao, B., Xu, P., Shi, Y., Tong, Y., Zhou, Z., Zeng, Y.: Preference-aware task assignment in on-demand taxi dispatching: an online stable matching approach. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, pp. 2245–2252 (2019)

   Google Scholar 

6. Kujansuu, E., Lindberg, T., M’akinen, E.: The stable roommates problem and chess tournament pairings. Divulgaciones Matemáticas 7(1), 19–28 (1999)

   Google Scholar 

7. Roth, A.E., Sönmez, T., Ünver, M.U.: Pairwise kidney exchange. J. Econ. Theory 125(2), 151–188 (2005)

   Google Scholar 

8. Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17, 449–467 (1965)

   Article  MathSciNet  Google Scholar 

9. Preis, R.: Linear time 1/2-approximation algorithm for maximum weighted matching in general graphs. STACS 99, 259–269 (1999)

   Article  MathSciNet  Google Scholar 

10. Drake, D.E., Hougardy, S.: A simple approximation algorithm for the weighted matching problem. Inform. Process. Lett. 85(4), 211–213 (2003)

    Article  MathSciNet  Google Scholar 

11. Drake, D.E., Hougardy, S.: Improved linear time approximation algorithms for weighted matchings. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 14–23 (2003)

    Google Scholar 

12. Duan, R., Pettie, S.: Approximating maximum weight matching in near-linear time. In: 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pp. 673–682 (2010)

    Google Scholar 

13. Koana, T., Korenwein, V., Nichterlein, A., Zschoche, P.: Data reduction for maximum matching on real-world graphs: theory and experiments (2018). arXiv preprint

    Google Scholar 

14. Wøhlk, S., Laporte, G.: Computational comparison of several greedy algorithms for the minimum cost perfect matching problem on large graphs. Comput. Oper. Res. 87, 107–113 (2017)

    Article  MathSciNet  Google Scholar 

15. von Luxburg, U.: A tutorial on spectral clustering. Statist. Comput. 17(4), 395–416 (2007)

    Article  MathSciNet  Google Scholar 

16. Shi, J., Malik, J.: Normalized cuts and image segmentation. In: Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol. 22, no. 8, pp. 888–905 (2000)

    Google Scholar 

17. Wu, Z., Leahy, R.: An optimal graph theoretic approach to data clustering: theory and its application to image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 15(11), 1101–1113 (1993)

    Article  Google Scholar 

18. Sarkar, S., Soundararajan, P.: Supervised learning of large perceptual organization: graph spectral partitioning and learning automata. IEEE Trans. Pattern Anal. Mach. Intell. 22(5), 504–525 (2000)

    Article  Google Scholar 

19. Hagen, L., Kahng, A.B.: New spectral methods for ratio cut partitioning and clustering. IEEE Trans. Computer Aided Design Integr. Circ. Syst. 11(9), 1074–1085 (1992)

    Article  Google Scholar 

20. Blondel, V.D., Guillaume, J.L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. J. Statist. Mech. Theory Experim. 2008, 10 (2008)

    MATH  Google Scholar 

21. Clauset, A., Newman, M.E., Moore, C.: Finding community structure in very large networks. Phys. Rev. E 70, 6 (2004)

    Article  Google Scholar 

22. Newman, M.E., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69, 2 (2004)

    Google Scholar 

23. Leskovec, J., Mcauley, J.: Learning to discover social circles in ego networks. In: Pereira, F., Burges, C.J.C., Bottou, L., Weinberger, K.Q. (eds.) Advances in Neural Information Processing Systems. vol. 25. Curran Associates, Inc. (2012). https://proceedings.neurips.cc/paper/2012/file/7a614fd06c325499f1680b9896beedeb-Paper.pdf

24. Rozemberczki, B., Davies, R., R.S., Sutton, C.: Gemsec: Graph embedding with self clustering. In: Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pp. 65–72 (2019)

    Google Scholar 

25. Rozemberczki, B.C.A., Sarkar, R.: Multi-scale attributed node embedding (2019). arXiv preprint

    Google Scholar 

26. Rozemberczki, B., Sarkar, R.: Characteristic functions on graphs: birds of a feather, from statistical descriptors to parametric models. In: Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pp. 1325–1334 (2020)

    Google Scholar 

Download references