IMSc Webinar

Approximation in (Poly-) Logarithmic Space

Arindam Biswas

IMSc

(Webinar; link: meet.google.com/vam-fhju-iyb)

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 Δ ∈ ℕ,

and

• 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.