• Approximation in (poly-) logarithmic space 

      Biswas, Arindam; Raman, Venkatesh; Saurabh, Saket (Journal article; Peer reviewed, 2020)
      We develop new approximation algorithms for classical graph and set problems in the RAM model under space constraints. As one of our main results, we devise an algorithm for d–Hitting Set that runs in time nO(d2+(d/ε)), ...
    • Parameterized streaming algorithms for min-ones d-SAT 

      Agrawal, Akanksha; Bonnet, Édouard; Curticapean, Radu; Miltzow, Tillmann; Saurabh, Saket; Biswas, Arindam; Brettell, Nick; Marx, Dániel; Raman, Venkatesh (Journal article; Peer reviewed, 2019)
      In this work, we initiate the study of the Min-Ones d-SAT problem in the parameterized streaming model. An instance of the problem consists of a d-CNF formula F and an integer k, and the objective is to determine if F has ...
    • Subexponential Algorithms for Partial Cover Problems 

      Fomin, Fedor; Lokshtanov, Daniel; Raman, Venkatesh; Saurabh, Saket (Peer reviewed; Journal article, 2009)
      Partial Cover problems are optimization versions of fundamental and well studied problems like {\sc Vertex Cover} and {\sc Dominating Set}. Here one is interested in covering (or dominating) the maximum number of edges (or ...