Thursday, July 30 2020
11:30 - 12:30

IMSc Webinar

Approximation in (Poly-) Logarithmic Space

Arindam Biswas


(Webinar; link:

We consider the question of identifying problems that admit approximation algorithms which run in polynomial time and use polylogarithmic space.

In this talk, we will look at

• a factor-2 approximation algorithm for Vertex Cover restricted to graphs with maximum degree Δ which runs in polynomial time and uses O(log n) bits of space for any constant Δ ∈ ℕ,


• a factor-O((1 / ε) n^ε) (1 ≥ ε > 0, arbitrary) approximation algorithm for d–Hitting Set which runs in time n^{O(1 / ε)} and uses O((1 / ε) log n) bits of space for any constant d ∈ ℕ.

Joint work with Venkatesh Raman, Saket Saurabh.

Download as iCalendar