Past Events

Masters Defense

Vertex Cover in The Sliding Window Model

 

Download as iCal file

Wednesday, June 16, 2021, 01:00pm - 03:00pm
 

Speaker: Sai Krishna Chaitanya Nalam Venkata Subrahmanya

Location : Remote via Zoom

Committee: 

Prof. Sepehr Assadi

Prof. Aaron Bernstein

Prof James Abello

Event Type: Masters Defense

Abstract: We study the problem of finding a minimum vertex cover for a graph in the sliding window model. The sliding window model is similar to the original streaming model where the edges of a graph whose vertices are known, arrive sequentially in a stream. However, in the sliding window model, only the recent $w$ elements (edges in the case of graph) of the stream are considered in computing the output. We are only allowed to use $o(w)$ space and hence all the recent $w$ elements of the stream cannot be stored. Therefore, when a new element is arrived the oldest element goes out of the window. This implicit deletion makes the sliding window model harder when compared to the original streaming model. In this work, we observe that the $(3+\eps)$-approximation algorithm ($\eps \in (0,1)$) for maximum matching in the sliding window model can give a $(6+\eps)$-approximation for the minimum vertex cover problem in the sliding window model. We give a counterexample to the existing analysis of a $(4+\eps)$-approximation algorithm for the minimum vertex cover problem in the sliding window model and provide a correct analysis for the same algorithm. Finally, we come up with a $(3+\eps)$-approximation algorithm for the minimum vertex cover problem in the sliding window model using $\Tilde{O}(n)$ space, where $\thicksim$ encompasses $\frac{1}{\eps}, \log n$ factors with $n$ being the number of vertices in the graph.

: 

 

Zoom details:
Join Zoom Meeting
https://rutgers.zoom.us/j/7255989573?pwd=SktERkU0UmhJZ2h2ckFQSVRaT0dpZz09

Meeting ID: 725 598 9573
Password: 460280