Online Algorithms and Approximation Algorithms for Vertex Cover and Other Variants

Download or read book Online Algorithms and Approximation Algorithms for Vertex Cover and Other Variants written by Pulok Rahman and published by . This book was released on 2022 with total page 0 pages. Available in PDF, EPUB and Kindle. Book excerpt: Vertex Cover is a NP Complete Problem that has been studied upon. Vertex Cover is a subset of the vertices of the graph where such that for every edge in the graph would intersect with at least one of vertices in the vertex cover. The challenge comes from it being NP Complete, but it has wide variety of applications that it's worth the risk. Those applications include having enough security cameras to have view of all the hallways and even into biology. This paper will attempt to solve this problem with approximation algorithms and online algorithms. The goal will look at how the competitive ratio fluctuates with the slightest change of the algorithm or changing the input to looking at certain type of graph. Some interesting results occur where ratio might diverge to infinity, stay at 2, or improve to 2-r. We begin by modifying the original approximation algorithm into an online algorithm. Then we look at an online algorithm where edges are introduced one at a time. The result is that the competitive ratio is just two. Then we look at an online algorithm where it attempts to go optimal at each step. This one diverges to infinity strangely enough. Finally, we attempt to create an efficient online algorithm for trees. The interesting part about an online algorithm for trees is that one does not where the leaves are located because the inputs come at one vertex at a time, and the usual efficient vertex cover of a tree requires knowing the leaves' locations.