Source author record

Aniket Basu Roy

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Approximate Covering with Lower and Upper Bounds via LP Rounding

In this paper, we study the lower- and upper-bounded covering (LUC) problem, where we are given a set $P$ of $n$ points, a collection $\mathcal{B}$ of balls, and parameters $L$ and $U$ . The goal is to find a minimum-sized subset $\mathcal{B}'\subseteq \mathcal{B}$ and an assignment of the points in $P$ to $\mathcal{B}'$ , such that each point $p\in P$ is assigned to a ball that contains $p$ and for each ball $B_i\in \mathcal{B}'$ , at least $L$ and at most $U$ points are assigned to $B_i$ . We obtain an LP rounding based constant approximation for LUC by violating the lower and upper bound constraints by small constant factors and expanding the balls by again a small constant factor. Similar results were known before for covering problems with only the upper bound constraint. We also show that with only the lower bound constraint, the above result can be obtained without any lower bound violation. Covering problems have close connections with facility location problems. We note that the known constant-approximation for the corresponding lower- and upper-bounded facility location problem, violates the lower and upper bound constraints by a constant factor.

preprint2016arXiv

The Runaway Rectangle Escape Problem

Motivated by the applications of routing in PCB buses, the Rectangle Escape Problem was recently introduced and studied. In this problem, we are given a set of rectangles $\mathcal{S}$ in a rectangular region $R$ , and we would like to extend these rectangles to one of the four sides of $R$ . Define the density of a point $p$ in $R$ as the number of extended rectangles that contain $p$ . The question is then to find an extension with the smallest maximum density. We consider the problem of maximizing the number of rectangles that can be extended when the maximum density allowed is at most $d$ . It is known that this problem is polynomially solvable for $d = 1$ , and NP-hard for any $d \geq 2$ . We consider approximation and exact algorithms for fixed values of $d$ . We also show that a very special case of this problem, when all the rectangles are unit squares from a grid, continues to be NP-hard for $d = 2$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.