A MapReduce Algorithm for Minimum Vertex Cover Problems and Its Randomization
Keywords:MapReduce, minimum vertex cover, Hadoop, optimization, algorithm design, randomized algorithm
AbstractMapReduce is a programming paradigm for large-scale distributed information processing. This paper proposes a MapReduce algorithm for the minimum vertex cover problem, which is known to be NP-hard. The MapReduce algorithm can efficiently obtain a minimal vertex cover in a small number of rounds. We show the effectiveness of the algorithm, through experimental evaluation and comparison with exact and approximate algorithms that it demonstrates high quality in a small number of MapReduce rounds. We also confirm from experimentation that the algorithm has good scalability, allowing high-quality solutions under restricted computation times due to increased graph size. Moreover, we extend our algorithm to randomized one to obtain good expected approximate ratio.
Download data is not yet available.
How to Cite
Nakamura, M., Kinjo, D., & Yoshida, T. (2021). A MapReduce Algorithm for Minimum Vertex Cover Problems and Its Randomization. COMPUTING AND INFORMATICS, 39(5), 952–972. https://doi.org/10.31577/cai_2020_5_952