Browsing Bergen Open Research Archive by Author "Raman, Venkatesh"
Now showing items 1-3 of 3
-
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 ...