Gunjan Kumar

Anand Deo

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

A-201 (STCS Seminar Room)

Abstract

We present algorithmic applications of an approximate version of Caratheodory's theorem. The theorem states that given a set of vectors $X$ in $\mathbb{R^d}$, for every vector in the convex hull of $X$ there exists an $\epsilon$-close (under the $p$-norm distance, for $2 \le p < \infty $ ) vector that can be expressed as a convex combination of at most b vectors of $X$, where the bound b depends on $\epsilon$ and the norm p and is independent of the dimension $d$. This theorem can be derived by instantiating Maurey's lemma, early references to which can be found in the work of Pisier (1981) and Carl(1985). However, in this paper we present a self-contained proof of this result.

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.

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.

© Copyright 2023, School of Technology and Computer Science | TIFR - All Rights Reserved | Login