Source author record

Supantha Pandit

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 Distributed, Parallel, and Cluster Computing

Catalog footprint

Research overview

3works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Collaborative Dispersion by Silent Robots

In the dispersion problem, a set of $k$ co-located mobile robots must relocate themselves in distinct nodes of an unknown network. The network is modeled as an anonymous graph $G=(V,E)$ , where the nodes of the graph are not labeled. The edges incident to a node $v$ with degree $d$ are labeled with port numbers in the range $0,1, \cdots, d-1$ at $v$ . The robots have unique ids in the range $[0,L]$ , where $L \ge k$ , and are initially placed at a source node $s$ . Each robot knows only its own id but does not know the ids of the other robots or the values of $L,k$ . The task of dispersion was traditionally achieved with the assumption of two types of communication abilities: (a) when some robots are at the same node, they can communicate by exchanging messages between them (b) any two robots in the network can exchange messages between them. In this paper, we ask whether this ability of communication among co-located robots is necessary to achieve dispersion. We show that even if the ability of communication is not available, the task of dispersion by a set of mobile robots can be achieved in a much weaker model where a robot at a node $v$ has the access of following very restricted information at the beginning of any round: (1) am I alone at $v$ ? (2) the number of robots at $v$ increased or decreased compare to the previous round? We propose a deterministic algorithm that achieves dispersion on any given graph $G=(V,E)$ in time $O\left( k\log L+k^2 \log Δ\right)$ , where $Δ$ is the maximum degree of a node in $G$ . Each robot uses $O(\log L+ \log Δ)$ additional memory. We also prove that the task of dispersion cannot be achieved by a set of mobile robots with $o(\log L + \log Δ)$ additional memory.

preprint2016arXiv

Covering segments with unit squares

We study several variations of line segment covering problem with axis-parallel unit squares in $I\!\!R^2$ . A set $S$ of $n$ line segments is given. The objective is to find the minimum number of axis-parallel unit squares which cover at least one end-point of each segment. The variations depend on the orientation and length of the input segments. We prove some of these problems to be NP-complete, and give constant factor approximation algorithms for those problems. For some variations, we have polynomial time exact algorithms. For the general version of the problem, where the segments are of arbitrary length and orientation, and the squares are given as input, we propose a factor 16 approximation result based on multilevel linear programming relaxation technique, which may be useful for solving some other problems. Further, we show that our problems have connections with the problems studied by Arkin et al. 2015 on conflict-free covering problem. Our NP-completeness results hold for more simplified types of objects than those of Arkin et al. 2015.

preprint2016arXiv

Faster Approximation for Maximum Independent Set on Unit Disk Graph

Maximum independent set from a given set $D$ of unit disks intersecting a horizontal line can be solved in $O(n^2)$ time and $O(n^2)$ space. As a corollary, we design a factor 2 approximation algorithm for the maximum independent set problem on unit disk graph which takes both time and space of $O(n^2)$ . The best known factor 2 approximation algorithm for this problem runs in $O(n^2 \log n)$ time and takes $O(n^2)$ space [Jallu and Das 2016, Das et al. 2016].

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.