کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
7543468 | 1489488 | 2018 | 31 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Purely combinatorial approximation algorithms for maximum k-vertex cover in bipartite graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We study the polynomial time approximation of the NP-hard maxk-vertex cover problem in bipartite graphs and propose purely combinatorial approximation algorithms. The main result of the paper is a simple combinatorial algorithm and a computer-assisted analysis of its approximation guarantee giving strong evidence that the worst approximation ratio achieved is bounded below by 0.821. We also study two simpler strategies with provable approximation ratios of 23 and 3447â0.72 respectively that already beat the only such known algorithm, namely the greedy approach which guarantees ratio (1â1e)â0.632. Our principal motivation is to bring a satisfactory answer in the following question: to what extent combinatorial methods for maxk-vertex cover compete with linear programming ones?
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 27, February 2018, Pages 26-56
Journal: Discrete Optimization - Volume 27, February 2018, Pages 26-56
نویسندگان
Ãdouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, Georgios Stamoulis,