文章基本信息

标题：A MapReduce Algorithm for Minimum Vertex Cover Problems and Its Randomization
本地全文：下载
作者：Morikazu Nakamura ; Daiki Kinjo ; Takeo Yoshida 等
期刊名称：COMPUTING AND INFORMATICS
印刷版ISSN：1335-9150
出版年度：2020
卷号：39
期号：5
页码：952-972
DOI：10.31577/cai_2020_5_952
出版社：COMPUTING AND INFORMATICS
摘要：MapReduce 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.
其他摘要：MapReduce 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.
关键词：MapReduce; minimum vertex cover; Hadoop; optimization; algorithm design; randomized algorithm
其他关键词：MapReduce;minimum vertex cover;Hadoop;optimization;algorithm design;randomized algorithm