5 papers
Online Algorithms for Geometric Independent Set
Minati De, Satyam Singh
In the classical online model, the maximum independent set problem admits an lower bound on the competitive ratio even for interval graphs, motivating the study of the prob…
Online Hitting of Unit Balls and Hypercubes in using Points from
Minati De, Satyam Singh
We consider the online hitting set problem for the range space , where the point set is known beforehand, but the set of geometric objects is…
Online Hitting Set for Axis-Aligned Squares
Minati De, Satyam Singh, Csaba D. Tóth
We are given a set of points in the plane, and a sequence of axis-aligned squares that arrive in an online fashion. The online hitting set problem consists of maintaining,…
Online Hitting Sets for Disks of Bounded Radii
Minati De, Satyam Singh, Csaba D. Tóth
We present algorithms for the online minimum hitting set problem in geometric range spaces: given a set of points in the plane and a sequence of geometric objects that arri…
New Lower Bound and Algorithms for Online Geometric Hitting Set Problem
Minati De, Ratnadip Mandal, Satyam Singh
The hitting set problem is one of the fundamental problems in combinatorial optimization and is well-studied in offline setup. We consider the online hitting set problem, where onl…