2020/01/17 by Deepak Ponvel Chermakani, Chermakani, Deepak Ponvel
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.2001.06169
openalex publication_date 2020/01/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider (n+1) runners with given constant unique integer speeds running\nalong the circumference of a circle whose circumferential length is one, and\nall runners starting from the same point. We define and give lower bounds to a\nfirst problem PMAX of finding, for every runner r, the maximum number of\nrunners that can be simultaneously separated from runner r by a distance of\natleast d. For d=1/(2^(floor(lg(n)))), a lower bound for PMAX is ( n -\n((n-1)/floor(lg(n))) ), which makes the fraction of simultaneously separated\nrunners tend to 1 as n tends to infinity. Next, we define and give upper bounds\nto a second problem ISOLATE of finding, for every runner r, the minimum number\nof steps needed to isolate r, assuming that the runners that can be\nsimultaneously separated from r by atleast d, are removed at each step. For\nd=1/(2^(floor(lg(n)))), an upper bound for ISOLATE is ( lg(n -\n1)/lg(floor(lg(n))) ).\n