Source author record

Somnath Kundu

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

ResearcherUnclaimed source record

Discrete Mathematics math.CO math.OC math.PR

Catalog footprint

Research overview

2works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Lower Bounds for Shoreline Searching with 2 or More Robots

Searching for a line on the plane with $n$ unit speed robots is a classic online problem that dates back to the 50's, and for which competitive ratio upper bounds are known for every $n\geq 1$ . In this work we improve the best lower bound known for $n=2$ robots from 1.5993 to 3. Moreover we prove that the competitive ratio is at least $\sqrt{3}$ for $n=3$ robots, and at least $1/\cos(π/n)$ for $n\geq 4$ robots. Our lower bounds match the best upper bounds known for $n\geq 4$ , hence resolving these cases. To the best of our knowledge, these are the first lower bounds proven for the cases $n\geq 3$ of this several decades old problem.

preprint2020arXiv

The Unit Acquisition Number of Binomial Random Graphs

Let $G$ be a graph in which each vertex initially has weight 1. In each step, the unit weight from a vertex $u$ to a neighbouring vertex $v$ can be moved, provided that the weight on $v$ is at least as large as the weight on $u$ . The unit acquisition number of $G$ , denoted by $a_u(G)$ , is the minimum cardinality of the set of vertices with positive weight at the end of the process (over all acquisition protocols). In this paper, we investigate the Erdős-Rényi random graph process $(\mathcal{G}(n,m))_{m =0}^{N}$ , where $N = {n \choose 2}$ . We show that asymptotically almost surely $a_u(\mathcal{G}(n,m)) = 1$ right at the time step the random graph process creates a connected graph. Since trivially $a_u(\mathcal{G}(n,m)) \ge 2$ if the graphs is disconnected, the result holds in the strongest possible sense.

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.