ترجمه فارسی توضیحات (ترجمه ماشینی)
یک الگوریتم تقریبی 2 1/10 برای تعمیم مسئله مجموعه ای از لبه های وزن دار
ما تقریبپذیری مسئله مجموعه وزندار بر لبه را مطالعه میکنیم. اگرچه حتی حالت وزننشده NP-Complete است، در این مورد، یک راهحل با اندازه حداکثر دو برابر حداقل را میتوان بهدلیل رابطه نزدیک آن با حداقل تطابق حداکثر، به طور مؤثر محاسبه کرد. با این حال، در مورد وزن، چنین رابطه خوبی وجود ندارد. در این مقاله، پس از اینکه نشان دادیم تسلط لبه وزنی به اندازه مسئله پوشش راس وزنی به خوبی مورد مطالعه قرار گرفته سخت است، یک استراتژی طبیعی را در نظر می گیریم که مجموعه ای از تسلط بر لبه را به پوشش لبه کاهش می دهد.
A 2 1/10-Approximation Algorithm for a Generalization of the Weighted Edge-Dominating Set Problem
We study the approximability of the weighted edge-dominating set problem. Although even the unweighted case is NP-Complete, in this case a solution of size at most twice the minimum can be efficiently computed due to its close relationship with minimum maximal matching; however, in the weighted case such a nice relationship is not known to exist. In this paper, after showing that weighted edge domination is as hard to approximate as the well studied weighted vertex cover problem, we consider a natural strategy, reducingedge-dominating set to edge cover.
نقد و بررسیها
هنوز بررسیای ثبت نشده است.