Speaker: |
Gunjan Kumar |

Organiser: |
Anand Deo |

Date: |
Friday, 7 Oct 2016, 16:00 to 17:30 |

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

(Scan to add to calendar)

The approximate Caratheodory's theorem leads to an additive approximation algorithm for the normalized densest $k$-bipartite subgraph problem. Given a graph with n vertices and maximum degree $d$, the developed algorithm determines a $k \times k$ bipartite subgraph with density within $\epsilon$ (in the additive sense) of the optimal density in time $n^{O(\frac{log d}{\epsilon^2})}$.

This result appears in STOC 2015, titled `Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem' by Siddharth Barman.