Online Hitting Geometric Objects
Online Hitting Geometric Objects
Minati De
ASSISTANT PROFESSOR
DEPARTMENT OF MATHEMATICS
INDIAN INSTITUTE OF TECHNOLOGY DELHI
ABSTRACT
The hitting set problem is one of the most fundamental problems in combinatorial optimization. In this talk, we consider the online version of the problem where geometric objects arrive one at a time, and the goal is to maintain a hitting set of the minimum cardinality by making irrevocable decisions. We present some lower bounds and competitive algorithms for many exciting variants of the problem. We conclude the talk with a few open problems.