Weighted group search on the disk & improved lower bounds for priority evacuation
Konstantinos Georgiou, Xin Wang · Journal of Computer and System Sciences · 2025
We study weighted group search on a disk , where two unit-speed agents must locate a hidden target exactly distance 1 away (within a unit-radius disk), starting from the same point. Agents share findings instantly via the wireless model. The goal is to minimize the worst-case weighted average of their arrival times, with one agent weighted 1 and the other w ∈ [ 0 , 1 ] . This problem extends prior work on search on a line (with known optimal strategies) and the priority evacuation problem, which corresponds to w = 0 and still has a notable gap between upper and lower bounds. Our contributions are the following: (1) Upper bounds for all w , using refined known techniques. (2) A novel lower-bound framework using linear programming, inspired by metric embeddings, and (3) Improved bounds for priority evacuation, raising the lower bound from 4.38962 to 4.56798.