|
|
|
|
a (2 − ε)-approximation ratio for vertex cover problem on special graphs
|
|
|
|
|
|
|
|
نویسنده
|
yekezare n. ,zohrehbandian m. ,maghasedi m.
|
|
منبع
|
journal of linear and topological algebra - 2023 - دوره : 12 - شماره : 2 - صفحه:113 -118
|
|
چکیده
|
The vertex cover problem is a famous combinatorial problem, and its complexity has been heavily studied. it is known that it is hard to approximate to within any constant factor better than 2, while a 2-approximation for it can be trivially obtained. in this paper, new properties and new techniques are introduced which lead to approximation ratios smaller than 2 on special graphs; e.g. graphs for which their maximum cut values are less than 0.999|e|. in fact, we produce a (1.9997)-approximation ratio on graph g, where the (0.878)-approximation algorithm of the goemans-williamson for the maximum cut problem on g produces a value smaller than 0.877122|e|.
|
|
کلیدواژه
|
discrete optimization ,vertex cover problem ,complexity theory ,np-complete problems.
|
|
آدرس
|
islamic azad university, karaj branch, department of mathematics, iran, islamic azad university, karaj branch, department of mathematics, iran, islamic azad university, karaj branch, department of mathematics, iran
|
|
پست الکترونیکی
|
maghasedi@kiau.ac.ir
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Authors
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|