×

Analysing local algorithms in location-aware quasi-unit-disk graphs. (English) Zbl 1228.05273

Summary: A local algorithm with local horizon \(r\) is a distributed algorithm that runs in \(r\) synchronous communication rounds; here \(r\) is a constant that does not depend on the size of the network. As a consequence, the output of a node in a local algorithm only depends on the input within \(r\) hops from the node.
We give tight bounds on the local horizon for a class of local algorithms for combinatorial problems on unit-disk graphs (UDGs). Most of our bounds are due to a refined analysis of existing approaches, while others are obtained by suggesting new algorithms. The algorithms we consider are based on network decompositions guided by a rectangular tiling of the plane. The algorithms are applied to matching, independent set, graph colouring, vertex cover, and dominating set.
We also study local algorithms on quasi-UDGs, which are a popular generalisation of UDGs, aimed at more realistic modelling of communication between the network nodes. Analysing the local algorithms on quasi-UDGs allows one to assume that the nodes know their coordinates only approximately, up to an additive error. Despite the localisation error, the quality of the solution to problems on quasi-UDGs remains the same as for the case of UDGs with perfect location awareness. We analyse the increase in the local horizon that comes along with moving from UDGs to quasi-UDGs.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Åstrand, Matti; Floréen, Patrik; Polishchuk, Valentin; Rybicki, Joel; Suomela, Jukka; Uitto, Jara, A local 2-approximation algorithm for the vertex cover problem, (Proc. 23rd Symposium on Distributed Computing. Proc. 23rd Symposium on Distributed Computing, DISC 2009. Proc. 23rd Symposium on Distributed Computing. Proc. 23rd Symposium on Distributed Computing, DISC 2009, LNCS, vol. 5805 (2009), Springer), 191-205 · Zbl 1261.68161
[2] Åstrand, Matti; Suomela, Jukka, Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks, (Proc. 22nd Symposium on Parallelism in Algorithms and Architectures. Proc. 22nd Symposium on Parallelism in Algorithms and Architectures, SPAA 2010 (2010), ACM Press), 294-302
[3] Attiya, Hagit; Shachnai, Hadas; Tamir, Tami, Local labeling and resource allocation using preprocessing, SIAM Journal on Computing, 28, 4, 1397-1413 (1999) · Zbl 0940.68035
[4] Awerbuch, Baruch; Goldberg, Andrew V.; Luby, Michael; Plotkin, Serge A., Network decomposition and locality in distributed computation, (Proc. 30th Symposium on Foundations of Computer Science. Proc. 30th Symposium on Foundations of Computer Science, FOCS 1989 (1989), IEEE), 364-369
[5] Barrière, Lali; Fraigniaud, Pierre; Narayanan, Lata; Opatrny, Jaroslav, Robust position-based routing in wireless ad-hoc networks with irregular transmission ranges, Wireless Communications and Mobile Computing Journal, 3, 2, 141-153 (2003)
[6] Chávez, Edgar; Dobrev, Stefan; Kranakis, Evangelos; Opatrny, Jaroslav; Stacho, Ladislav; Urrutia, Jorge, Local construction of planar spanners in unit disk graphs with irregular transmission ranges, (Proc. 7th Latin American Theoretical Informatics Symposium. Proc. 7th Latin American Theoretical Informatics Symposium, LATIN 2006. Proc. 7th Latin American Theoretical Informatics Symposium. Proc. 7th Latin American Theoretical Informatics Symposium, LATIN 2006, LNCS, vol. 3887 (2006), Springer), 286-297 · Zbl 1145.68472
[7] Conway, John H.; Sloane, Neil J. A., Sphere Packings, Lattices and Groups (1988), Springer
[8] Croft, Hallard T.; Falconer, Kenneth J.; Guy, Richard K., Unsolved Problems in Geometry (1991), Springer · Zbl 0748.52001
[9] Czygrinow, Andrzej; Hańćkowiak, Michał; Wawrzyniak, Wojciech, Fast distributed approximations in planar graphs, (Proc. 22nd Symposium on Distributed Computing. Proc. 22nd Symposium on Distributed Computing, DISC 2008. Proc. 22nd Symposium on Distributed Computing. Proc. 22nd Symposium on Distributed Computing, DISC 2008, LNCS, vol. 5218 (2008), Springer), 78-92 · Zbl 1161.68865
[10] Czyzowicz, Jurek; Dobrev, Stefan; Fevens, Thomas; González-Aguilar, Hernán; Kranakis, Evangelos; Opatrny, Jaroslav; Urrutia, Jorge, Local algorithms for dominating and connected dominating sets of unit disk graphs with location aware nodes, (Proc. 8th Latin American Theoretical Informatics Symposium. Proc. 8th Latin American Theoretical Informatics Symposium, LATIN 2008. Proc. 8th Latin American Theoretical Informatics Symposium. Proc. 8th Latin American Theoretical Informatics Symposium, LATIN 2008, LNCS, vol. 4957 (2008), Springer), 158-169 · Zbl 1136.68453
[11] Czyzowicz, Jurek; Dobrev, Stefan; González-Aguilar, Hernán; Královič, Rastislav; Kranakis, Evangelos; Opatrny, Jaroslav; Stacho, Ladislav; Urrutia, Jorge, Local 7-coloring for planar subgraphs of unit disk graphs, Theoretical Computer Science, 412, 18, 1696-1704 (2011) · Zbl 1216.05155
[12] Czyzowicz, Jurek; Dobrev, Stefan; Kranakis, Evangelos; Opatrny, Jaroslav; Urrutia, Jorge, Local edge colouring of Yao-like subgraphs of unit disk graphs, Theoretical Computer Science, 410, 14, 1388-1400 (2009) · Zbl 1163.68032
[13] Doyle, Peter G.; Laurie Snell, J., (Random Walks and Electric Networks. Random Walks and Electric Networks, The Carus Mathematical Monographs, vol. 22 (1984), The Mathematical Association of America: The Mathematical Association of America Washington, DC, USA)
[14] Fejes Tóth, László, Lagerungen in der Ebene auf der Kugel und im Raum (1953), Springer · Zbl 0052.18401
[15] Patrik Floréen, Marja Hassinen, Joel Kaasinen, Petteri Kaski, Topi Musto, Jukka Suomela, Local approximability of max-min and min-max linear programs, Theory of Computing Systems (2010) (in press).; Patrik Floréen, Marja Hassinen, Joel Kaasinen, Petteri Kaski, Topi Musto, Jukka Suomela, Local approximability of max-min and min-max linear programs, Theory of Computing Systems (2010) (in press). · Zbl 1253.68360
[16] Floréen, Patrik; Hassinen, Marja; Kaski, Petteri; Suomela, Jukka, Tight local approximation results for max-min linear programs, (Proc. 4th Workshop on Algorithmic Aspects of Wireless Sensor Networks (Algosensors 2008). Proc. 4th Workshop on Algorithmic Aspects of Wireless Sensor Networks (Algosensors 2008), LNCS, vol. 5389 (2008), Springer), 2-17 · Zbl 1253.68360
[17] Floréen, Patrik; Kaasinen, Joel; Kaski, Petteri; Suomela, Jukka, An optimal local approximation algorithm for max-min linear programs, (Proc. 21st Symposium on Parallelism in Algorithms and Architectures. Proc. 21st Symposium on Parallelism in Algorithms and Architectures, SPAA 2009 (2009), ACM Press), 260-269 · Zbl 1253.68360
[18] Floréen, Patrik; Kaski, Petteri; Musto, Topi; Suomela, Jukka, Approximating max-min linear programs with local algorithms, (Proc. 22nd International Parallel and Distributed Processing Symposium, IPDPS 2008 (2008), IEEE) · Zbl 1253.68360
[19] Floréen, Patrik; Kaski, Petteri; Musto, Topi; Suomela, Jukka, Local approximation algorithms for scheduling problems in sensor networks, (Proc. 3rd Workshop on Algorithmic Aspects of Wireless Sensor Networks (Algosensors 2007). Proc. 3rd Workshop on Algorithmic Aspects of Wireless Sensor Networks (Algosensors 2007), LNCS, vol. 4837 (2008), Springer), 99-113
[20] Floréen, Patrik; Kaski, Petteri; Suomela, Jukka, A distributed approximation scheme for sleep scheduling in sensor networks, (Proc. 4th Conference on Sensor, Mesh and Ad Hoc Communications and Networks. Proc. 4th Conference on Sensor, Mesh and Ad Hoc Communications and Networks, SECON 2007 (2007), IEEE), 152-161
[21] Erich Friedman, Circles in squares, June 2002. http://www.stetson.edu/ efriedma/cirinsqu/; Erich Friedman, Circles in squares, June 2002. http://www.stetson.edu/ efriedma/cirinsqu/ · Zbl 1041.52009
[22] Goldsmith, Andrea, Wireless Communications (2005), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 1127.93327
[23] Marja Hassinen, Valentin Polishchuk, Jukka Suomela, Local 3-approximation algorithms for weighted dominating set and vertex cover in quasi unit-disk graphs, in: Proc. 2nd Workshop on Localized Algorithms and Protocols for Wireless Sensor Networks, LOCALGOS 2008, 2008, pp. V.9-V.12.; Marja Hassinen, Valentin Polishchuk, Jukka Suomela, Local 3-approximation algorithms for weighted dominating set and vertex cover in quasi unit-disk graphs, in: Proc. 2nd Workshop on Localized Algorithms and Protocols for Wireless Sensor Networks, LOCALGOS 2008, 2008, pp. V.9-V.12. · Zbl 1228.05273
[24] Hunt III, Harry B.; Marathe, Madhav V.; Radhakrishnan, Venkatesh; Ravi, S. S.; Rosenkrantz, Daniel J.; Stearns, Richard E., NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs, Journal of Algorithms, 26, 2, 238-274 (1998) · Zbl 0894.68105
[25] Kanj, Iyad A.; Perković, Ljubomir; Xia, Ge, Computing lightweight spanners locally, (Proc. 22nd Symposium on Distributed Computing. Proc. 22nd Symposium on Distributed Computing, DISC 2008. Proc. 22nd Symposium on Distributed Computing. Proc. 22nd Symposium on Distributed Computing, DISC 2008, LNCS, vol. 5218 (2008), Springer), 365-378 · Zbl 1161.68342
[26] Kanj, Iyad A.; Wiese, Andreas; Zhang, Fenghui, Local algorithms for edge colorings in UDGs, (Proc. 35th Workshop on Graph-Theoretic Concepts in Computer Science, WG 2009. Proc. 35th Workshop on Graph-Theoretic Concepts in Computer Science, WG 2009, LNCS, vol. 5911 (2010), Springer), 202-213 · Zbl 1273.68279
[27] Kaski, Petteri; Penttinen, Aleksi; Suomela, Jukka, Coordinating concurrent transmissions: a constant-factor approximation of maximum-weight independent set in local conflict graphs, Ad Hoc & Sensor Wireless Networks: An International Journal, 6, 3-4, 239-263 (2008)
[28] Kirchner, Kerstin; Wengerodt, Gerhard, Die dichteste Packung von \(36\) Kreisen in einem Quadrat, Beiträge zur Algebra und Geometrie, 25, 147-159 (1987) · Zbl 0647.52002
[29] Krishnamachari, Bhaskar, Networking Wireless Sensors (2005), Cambridge University Press: Cambridge University Press Cambridge, UK
[30] Fabian Kuhn, The price of locality: exploring the complexity of distributed coordination primitives, Ph.D. Thesis, ETH Zurich, 2005.; Fabian Kuhn, The price of locality: exploring the complexity of distributed coordination primitives, Ph.D. Thesis, ETH Zurich, 2005.
[31] Kuhn, Fabian; Moscibroda, Thomas; Wattenhofer, Roger, What cannot be computed locally!, (Proc. 23rd Symposium on Principles of Distributed Computing. Proc. 23rd Symposium on Principles of Distributed Computing, PODC 2004 (2004), ACM Press), 300-309 · Zbl 1321.68478
[32] Kuhn, Fabian; Moscibroda, Thomas; Wattenhofer, Roger, On the locality of bounded growth, (Proc. 24th Symposium on Principles of Distributed Computing. Proc. 24th Symposium on Principles of Distributed Computing, PODC 2005 (2005), ACM Press), 60-68 · Zbl 1314.68160
[33] Kuhn, Fabian; Moscibroda, Thomas; Wattenhofer, Roger, The price of being near-sighted, (Proc. 17th Symposium on Discrete Algorithms. Proc. 17th Symposium on Discrete Algorithms, SODA 2006 (2006), ACM Press), 980-989 · Zbl 1192.68044
[34] Kuhn, Fabian; Wattenhofer, Roger, Constant-time distributed dominating set approximation, Distributed Computing, 17, 4, 303-310 (2005) · Zbl 1264.68219
[35] Kuhn, Fabian; Wattenhofer, Roger; Zollinger, Aaron, Ad hoc networks beyond unit disk graphs, Wireless Networks, 14, 5, 715-729 (2008)
[36] Christoph Lenzen, Synchronization and symmetry breaking in distributed systems, Ph.D. Thesis, ETH Zurich, January 2011.; Christoph Lenzen, Synchronization and symmetry breaking in distributed systems, Ph.D. Thesis, ETH Zurich, January 2011.
[37] Christoph Lenzen, Yvonne Anne Oswald, Roger Wattenhofer, What can be approximated locally? TIK Report 331, ETH Zurich, Computer Engineering and Networks Laboratory, November 2010.; Christoph Lenzen, Yvonne Anne Oswald, Roger Wattenhofer, What can be approximated locally? TIK Report 331, ETH Zurich, Computer Engineering and Networks Laboratory, November 2010.
[38] Lenzen, Christoph; Wattenhofer, Roger, Leveraging Linial’s locality limit, (Proc. 22nd Symposium on Distributed Computing. Proc. 22nd Symposium on Distributed Computing, DISC 2008. Proc. 22nd Symposium on Distributed Computing. Proc. 22nd Symposium on Distributed Computing, DISC 2008, LNCS, vol. 5218 (2008), Springer), 394-407 · Zbl 1161.68344
[39] Lenzen, Christoph; Wattenhofer, Roger, Minimum dominating set approximation in graphs of bounded arboricity, (Proc. 24th Symposium on Distributed Computing. Proc. 24th Symposium on Distributed Computing, DISC 2010. Proc. 24th Symposium on Distributed Computing. Proc. 24th Symposium on Distributed Computing, DISC 2010, LNCS, vol. 6343 (2010), Springer), 510-524 · Zbl 1290.68130
[40] Linial, Nathan, Locality in distributed graph algorithms, SIAM Journal on Computing, 21, 1, 193-201 (1992) · Zbl 0787.05058
[41] Thomas Moscibroda, Locality, scheduling, and selfishness: algorithmic foundations of highly decentralized networks, Ph.D. Thesis, ETH Zurich, 2006.; Thomas Moscibroda, Locality, scheduling, and selfishness: algorithmic foundations of highly decentralized networks, Ph.D. Thesis, ETH Zurich, 2006.
[42] Naor, Moni; Stockmeyer, Larry, What can be computed locally?, SIAM Journal on Computing, 24, 6, 1259-1277 (1995) · Zbl 0845.68006
[43] Papadimitriou, Christos H.; Yannakakis, Mihalis, Linear programming without the matrix, (Proc. 25th Symposium on Theory of Computing. Proc. 25th Symposium on Theory of Computing, STOC 1993 (1993), ACM Press), 121-129 · Zbl 1310.90073
[44] Peikert, Ronald; Würtz, Diethelm; Monagan, Michael; de Groot, Claas, Packing circles in a square: a review and new results, (Proc. 15th IFIP Conference on System Modelling and Optimization, Zürich, Switzerland, September 1991. Proc. 15th IFIP Conference on System Modelling and Optimization, Zürich, Switzerland, September 1991, Lecture Notes in Control and Information Sciences, vol. 180 (1992), Springer), 45-54 · Zbl 0789.52002
[45] Peleg, David, Distributed Computing — A Locality-Sensitive Approach (2000), SIAM · Zbl 0959.68042
[46] Polishchuk, Valentin; Suomela, Jukka, A simple local 3-approximation algorithm for vertex cover, Information Processing Letters, 109, 12, 642-645 (2009) · Zbl 1214.68468
[47] Schaer, J., The densest packing of nine circles in a square, Canadian Mathematical Bulletin, 8, 273-277 (1965) · Zbl 0144.44303
[48] Šparl, Petra; Žerovnik, Janez, \(2\)-local \(4 / 3\)-competitive algorithm for multicoloring hexagonal graphs, Journal of Algorithms, 55, 1, 29-41 (2005) · Zbl 1068.68168
[49] Suomela, Jukka, Distributed algorithms for edge dominating sets, (Proc. 29th Symposium on Principles of Distributed Computing. Proc. 29th Symposium on Principles of Distributed Computing, PODC 2010 (2010), ACM Press), 365-374 · Zbl 1315.68276
[50] Jukka Suomela, Survey of local algorithms, 2011, Manuscript. http://www.iki.fi/jukka.suomela/local-survey; Jukka Suomela, Survey of local algorithms, 2011, Manuscript. http://www.iki.fi/jukka.suomela/local-survey · Zbl 1293.68306
[51] Urrutia, Jorge, Local solutions for global problems in wireless networks, Journal of Discrete Algorithms, 5, 3, 395-407 (2007) · Zbl 1130.05059
[52] Wang, Yu; Li, Xiang-Yang, Localized construction of bounded degree and planar spanner for wireless ad hoc networks, Mobile Networks and Applications, 11, 2, 161-175 (2006)
[53] Wengerodt, Gerhard, Die dichteste Packung von \(16\) Kreisen in einem Quadrat, Beiträge zur Algebra und Geometrie, 16, 173-190 (1983)
[54] Andreas Wiese, Local approximation algorithms in unit disk graphs, Master’s Thesis, Technische Universität Berlin, 2007.; Andreas Wiese, Local approximation algorithms in unit disk graphs, Master’s Thesis, Technische Universität Berlin, 2007.
[55] Wiese, Andreas; Kranakis, Evangelos, Impact of locality on location aware unit disk graphs, Algorithms, 1, 2-29 (2008) · Zbl 1202.05048
[56] Wiese, Andreas; Kranakis, Evangelos, Local maximal matching and local 2-approximation for vertex cover in UDGs, (Proc. 7th Conference on Ad-Hoc Networks & Wireless. Proc. 7th Conference on Ad-Hoc Networks & Wireless, AdHoc-NOW 2008. Proc. 7th Conference on Ad-Hoc Networks & Wireless. Proc. 7th Conference on Ad-Hoc Networks & Wireless, AdHoc-NOW 2008, LNCS, vol. 5198 (2008), Springer), 1-14
[57] Wiese, Andreas; Kranakis, Evangelos, Local construction and coloring of spanners of location aware unit disk graphs, Discrete Mathematics, Algorithms and Applications, 1, 4, 555-588 (2009) · Zbl 1194.05046
[58] Wiese, Andreas; Kranakis, Evangelos, Local PTAS for dominating and connected dominating set in location aware unit disk graphs, (Proc. 6th Workshop on Approximation and Online Algorithms. Proc. 6th Workshop on Approximation and Online Algorithms, WAOA 2008. Proc. 6th Workshop on Approximation and Online Algorithms. Proc. 6th Workshop on Approximation and Online Algorithms, WAOA 2008, LNCS, vol. 5426 (2009), Springer), 227-240 · Zbl 1209.68655
[59] Wiese, Andreas; Kranakis, Evangelos, Local PTAS for independent set and vertex cover in location aware unit disk graphs, Ad Hoc & Sensor Wireless Networks: An International Journal, 7, 3-4, 273-293 (2009) · Zbl 1209.68655
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.