Searching and Routing in Discrete and Continuous Domains (15w5084)

Arriving in Oaxaca, Mexico Sunday, October 11 and departing Friday October 16, 2015

Organizers

(Carleton University)

(University of Manitoba)

(Université Libre de Bruxelles)

Ian Munro (University of Waterloo)

Objectives

Specific directions of research and discussion consist of the following milestones:

Days 1 & 2: Mutual impacts between techniques from routing problems and techniques from searching problems. A number of results in searching problems are based on algebraic techniques [2,3,9,18,24,26]. As for routing problems, geometric techniques are used in most results [1,6,8,10,11,13-16,27]. We will study how algebraic techniques can be used to solve open routing problems as well as new variants of routing problems. We will also study how geometric techniques can be used to solve open searching problems as well as new variants of searching problems. The potential impact is significant: solve open problems and new variants of fundamental problems. Day 1 will be dedicated to survey presentations on searching problems and discussions on how the techniques presented can be used on routing problems. Day 2 will be dedicated to survey presentations on routing problems and discussions on how the techniques presented can be used on searching problems. To the best of our knowledge, there has been only one attempt in that direction [7].

Day 3: Improving spanning ratios and competitiveness of local routing algorithms for geometric spanners. Tight spanning ratios for infinite families of graphs are rather difficult to obtain. For most of the families, the spanning ratios can still be improved. This is the case for Yao graphs, $theta$-graphs and most types of Delaunay triangulations [8] for instance. For some families of graphs, such as Yao-Yao graphs [19,25], we do not even know whether they are spanners.

Once we know that a graph is a spanner, the goal is to find a local routing algorithm for it. Indeed, spanners are good candidates for local routing. For some spanners, we do not even know a local routing algorithm (e.g., the greedy spanner). For those spanners for which we know a local routing algorithm, the competitiveness of the existing algorithms is not optimal. During Day 3, we will have survey presentations about these problems and we will revisit them in regards of the techniques presented in the first milestone.

Day 4: Study the tradeoffs between different parameters. For this milestone, we want to focus on results that depend on one or more parameters. For instance, for the problem of searching on a line with a given upper bound $Lambda$ on the distance between the searcher and the target, the optimal strategy and its cost can be expressed in terms of $Lambda$ [9]. For the problem of searching on a line with a turning cost, the optimal strategy and its cost can be expressed in terms of the turning cost [18]. For the problem of searching for a target on m concurrent rays, the optimal strategy and its cost can be expressed in terms of m [5]. There is an upper bound on any $theta$-graph that can be described in terms of $theta$ [10,16] (in terms of the number of cones to be more precise). There is a similar result for Yao-graphs [7,12]. Let C be a convex curve. An upper bound on the spanning ratio of the Delaunay triangulation defined with respect to C can be expressed in terms of two parameters related to C [8].

These results are important as they describe the tradeoffs between different parameters, and their impact on the optimal solution and its cost. They also help understanding how much information does the agent need in order to be able to reach the target. On Day 4, we want explore other parameters in regards of the techniques presented in the first milestone. What is the appropriate way of describing how local an algorithm is (local vs global)? Or suppose the agent can store b bytes of information. What is the impact of these parameters on the optimal solution and on its cost?

Day 5: Research and wrap up. On Day 5, we will pursue the ongoing research and establish atimeline for the directions of research that will have shown to be promising.


References

[1] O. Aichholzer, S.W. Bae, L. Barba, P. Bose, M. Korman, A. van Renssen P. Taslakian, and S. Verdonschot. Theta-3 is connected. In CCCG, pages 205–210, 2013.

[2] G. Aloupis, J. Iacono, J. Lenchner, and O. Ozkan. Locating a line at unit distance with multiple agents. In TJJCCGG, 2012.

[3] S. Alpern, R. Fokkink, L. Gasieniec, R. Lindelauf, and V.S. Subrahmanian. Search Theory: A Game Theoretic Perspective. Springer Publishing Company, Incorporated, 2013.

[4] S. Alpern and S. Gal. The Theory of Search Games and Rendezvous. International Series in Operations Research & Management Science. Springer, 2003.

[5] R.A. Baeza-Yates, J.C. Culberson, and G.J.E. Rawlins. Searching in the plane. Inf. Comput., 106(2):234–252, 1993.

[6] L. Barba, P. Bose, J.-L. De Carufel, A. van Renssen, and S. Verdonschot. On the stretch factor of the theta-4 graph. In WADS, pages 109–120, 2013.

[7] L. Barba, P. Bose, M. Damian, R. Fagerberg, J. O’Rourke, A. van Renssen, P. Taslakian, and S. Verdonschot. New and improved spanning ratios for Yao graphs. ArXiv, (1307.5829), 2013.

[8] P. Bose, P. Carmi, S. Collette, and M. Smid. On the stretch factor of convex delaunay graphs. JoCG, 1(1):41–56, 2010.

[9] P. Bose, J.-L. De Carufel, and S. Durocher. Revisiting the problem of searching on a line. In ESA, pages 205–216, 2013.

[10] P. Bose, J.-L. De Carufel, P. Morin, A. van Renssen, and S. Verdonschot. Optimal bounds on theta-graphs: More is not always better. In CCCG, pages 305–310, 2012.

[11] P. Bose and J.M. Keil. On the stretch factor of the constrained delaunay triangulation. In ISVD, pages 25–31, 2006.

[12] P. Bose, A. Maheshwari, G. Narasimhan, M. Smid, and N. Zeh. Approximating geometric bottleneck shortest paths. Comput. Geom., 29(3):233–249, 2004.

[13] P. Bose and P. Morin. Competitive online routing in geometric graphs. Theor. Comput. Sci., 324(2-3):273–288, 2004.

[14] P. Bose and P. Morin. Online routing in triangulations. SIAM J. Comput., 33(4):937–951, 2004.

[15] P. Bose, P. Morin, A. van Renssen, and S. Verdonschot. The theta-5 graph is a spanner. In WG, 2013.

[16] P. Bose, A. van Renssen, and S. Verdonschot. On the spanning ratio of theta-graphs. In WADS, pages 182–194, 2013.

[17] M. Broom. Interactions between searching predators and hidden prey. In S. Alpern, R. Fokkink, L. Gasieniec, R. Lindelauf, and V.S. Subrahmanian, editors, Search Theory: A Game Theoretic Perspective. Springer Publishing Company, Incorporated, 2013.

[18] E. Demaine, S.P. Fekete, and S. Gal. Online searching with turn cost. Theor. Comput. Sci., 361(2-3):342–355, 2006.

[19] E. Demaine, J.B. Mitchell, and J. O’Rourke. Yao-Yao graph a spanner? (problem 70). In The Open Problems Project, 2008.

[20] S. Gal. Search games. In Louis Anthony Cox, Jr., editor, Wiley Encyclopedia of Operations Research and Management Science. Wiley, 2011.

[21] W. Huang, S. Chen, and W. Wang. Navigation in spatial networks: A survey. Physica A: Statistical Mechanics and its Applications, 2013. in press.

[22] I. Kanj. Geometric spanners: Recent results and open directions. In ICCIT, pages 78–82, 2013.

[23] S. Kinsella and D.M. Ramsey. 17 a model of partnership formation with friction and multiple criteria. In S.Alpern, R. Fokkink, L. Gasieniec, Roy Lindelauf, and V.S. Subrahmanian, editors, Search Theory: A Game Theoretic Perspective. Springer Publishing Company, Incorporated, 2013.

[24] E. Langetepe. On the optimality of spiral search. In SODA, pages 1–12, 2010.

[25] M. Li, P.-J. Wan, Y. Wang, and O. Frieder. Sparse power efficient topology for wireless networks. In HICSS, pages 3839–3848, 2002.

[26] A. Lopez-Ortiz and S. Schuierer. The ultimate strategy to search on m rays? Theor. Comput. Sci., 261(2):267–295, 2001.

[27] G. Narasimhan and M. Smid. Geometric spanner networks. Cambridge University Press, 2007.

[28] D. Peleg. Distributed Computing: A Locality-Sensitive Approach. Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, 2000.

[29] Y. Wang. Topology control for wireless sensor networks. In Yingshu Li, MyT. Thai, and Weili Wu, editors, Wireless Sensor Networks and Applications, pages 113–147. Springer, 2008.

[30] W. Wu and Z. Zhang. Geometric optimization in wireless networks. In Handbook of Combinatorial Optimization, pages 1415–1457. Springer New York, 2013.