Access Restriction

Author Delbot, Franois ♦ Laforest, Christian
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2011
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Differential approximation ♦ Mean analysis ♦ Vertex cover ♦ Worst case approximation
Abstract The vertex cover is a well-known NP-complete minimization problem in graphs that has received a lot of attention these last decades. Many algorithms have been proposed to construct vertex cover in different contexts (offline, online, list algorithms, etc.) leading to solutions of different level of quality. This quality is traditionally measured in terms of approximation ratio, that is, the worst possible ratio between the quality of the solution constructed and the optimal one. For the vertex cover problem the range of such known ratios are between 2 (conjectured as being the smallest constant ratio) and Δ, the maximum degree of the graph. Based on this measure of quality, the hierarchy is almost clear (the smaller the ratio is, the better the algorithm is). In this article, we show that this measure, although of great importance, is too macroscopic and does not reflect the practical behavior of the methods. We prove this by analyzing (known and recent) algorithms running on a particular class of graphs: the paths. We obtain closed and exact formulas for the mean of the sizes of vertex cover constructed by these different algorithms. Then, we assess their quality experimentally in several well-chosen class of graphs (random, regular, trees, BHOSLIB benchmarks, trap graphs, etc.). The synthesis of all these results lead us to formulate a “practical hierarchy” of the algorithms. We remark that it is, more or less, the opposite to the one only based on approximation ratios, showing that worst-case analysis only gives partial information on the quality of an algorithm.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2010-11-05
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 15
Page Count 27
Starting Page 1.1
Ending Page 1.27

Open content in new tab

   Open content in new tab
Source: ACM Digital Library