查看文章

In 2005, Demange and Paschos proposed in [M. Demange, V.Th. Paschos, On-line vertex-covering, Theoret. Comput. Sci. 332 (2005) 83–108] an online algorithm (noted LR here) for the classical vertex cover problem. They shown that, for any graph of maximum degree Δ, LR constructs a vertex cover whose size is at most Δ times the optimal one (this bound is tight in the worst case). Very recently, two of the present authors have shown in [F. Delbot, C. Laforest, A better list heuristic for vertex cover, Inform. Process. Lett. 107 (2008) 125–127] that LR has interesting properties (it is a good “list algorithm” and it can easily be distributed). In addition, LR has good experimental behavior in spite of its Δ approximation (or competitive) ratio and the fact that it can be executed without the knowledge of the full instance at the beginning. In this paper we analyze it deeper and we show that LR has good “average” performances …