Speaker: |
Sumedh Vinod Tirodkar |

Organiser: |
Phani Raj Lolakapuri |

Date: |
Friday, 27 Oct 2017, 17:15 to 18:15 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

We begin by giving a two-pass (1/2 + 1/16)-approximation algorithm for triangle-free graphs and a two-pass (1/2 + 1/32)-approximation algorithm for general graphs; these improve the approximation ratios of 1/2 + 1/52 for bipartite graphs and 1/2 + 1/140 for general graphs by Konrad, Magniez, and Mathieu. In three passes, we achieve approximation ratios of 1/2 + 1/10 for triangle-free graphs and 1/2 + 1/19.753 for general graphs. We also give a multi-pass algorithm where we bound the number of passes precisely---we give a (2/3 -\epsilon)-approximation algorithm that uses 2/(3\epsilon) passes for triangle-free graphs and 4/(3\epsilon) passes for general graphs. Our algorithms are simple and combinatorial, use O(n \log(n)) space, and have O(1) update time per edge.

We extend the multipass algorithm to give a (3/4-\epsilon)-approximation algorithm that uses O(\log(1/\epsilon)/\epsilon) passes. This algorithm gives ideas for an (1-\epsilon)-approximation deterministic algorithm. Note that there is no known deterministic algorithm for general graphs which achieves (1-\epsilon)-approximation in constant number of passes.