CSE: State of art seminar - Supantha Pandit

Topic: A Study on Covering Objects by Axis Parallel Lines in Higher Dimensions

Speaker: Supantha Pandit

Date and Time: 30th April, 2012, Lecture Hall 3, 4:15 pm

Abstract:
Set cover and hitting set are two fundamental computational problems. These problems are known to be NP-complete. Therefore, researchers have focused on designing approximation algorithms for these problems. There is an O(log n) greedy algorithm for these problems and this bound has been proved to be tight. Some special cases of set cover problem that arises from geometric settings have better performance ratios. In this research proposal we investigate a special case, the point cover problem: Given a set of points in d-dimension, the goal is to find a set of minimum number of axis parallel lines such that each point lies on at least one line. This problem has been proved to be NP-complete for dimension >=3. There are successive improvements in the approximation factor for this special case. There is a simple factor d rounding algorithm, a (d-1)-factor approximation algorithm and (d/2)-factor approximation algorithm for the above problem. Here we outline an approach that may possibly lead to a better approximation factor.

In addition to this we are also considering two related problems in 2-dimension. First, Given a set of horizontal line segments, find a set of minimum number of axis parallel lines such that each segment is hit by at least one line and second given a set of rectangles, find minimum number of axis parallel lines that hit all rectangles.