nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Patrolling a Path Connecting a Set of Points with Unbalanced Frequencies of Visits

verfasst von : Huda Chuangpishit, Jurek Czyzowicz, Leszek Gąsieniec, Konstantinos Georgiou, Tomasz Jurdziński, Evangelos Kranakis

Erschienen in: SOFSEM 2018: Theory and Practice of Computer Science

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Patrolling consists of scheduling perpetual movements of a collection of mobile robots, so that each point of the environment is regularly revisited by any robot in the collection. In previous research, it was assumed that all points of the environment needed to be revisited with the same minimal frequency.

In this paper we study efficient patrolling protocols for points located on a path, where each point may have a different constraint on frequency of visits. The problem of visiting such divergent points was recently posed by Gąsieniec et al. in [14], where the authors study protocols using a single robot patrolling a set of n points located in nodes of a complete graph and in Euclidean spaces.

The focus in this paper is on patrolling with two robots. We adopt a scenario in which all points to be patrolled are located on a line. We provide several approximation algorithms concluding with the best currently known \(\sqrt{3}\)-approximation.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Multivendor Deployment Integration for Future Mobile Networks

Nächstes Kapitel Exploring Graphs with Time Constraints by Unreliable Collections of Mobile Robots

Alshamrani, S., Kowalski, D.R., Gąsieniec, L.: How reduce max algorithm behaves with symptoms appearance on virtual machines in clouds. In: Proceedings of IEEE International Conference CIT/IUCC/DASC/PICOM, pp. 1703–1710 (2015)

Baruah, S.K., Cohen, N.K., Plaxton, C.G., Varvel, D.A.: Proportionate progress: a notion of fairness in resource allocation. Algorithmica 15(6), 600–625 (1996)MathSciNetCrossRefMATH

Baruah, S.K., Lin, S.-S.: Pfair scheduling of generalized pinwheel task systems. IEEE Trans. Comput. 47(7), 812–816 (1998)MathSciNetCrossRef

Bender, M.A., Fekete, S.P., Kröller, A., Mitchell, J.S.B., Liberatore, V., Polishchuk, V., Suomela, J.: The minimum backlog problem. Theoret. Comput. Sci. 605, 51–61 (2015)MathSciNetCrossRefMATH

Bodlaender, M.H.L., Hurkens, C.A.J., Kusters, V.J.J., Staals, F., Woeginger, G.J., Zantema, H.: Cinderella versus the wicked stepmother. In: Baeten, J.C.M., Ball, T., de Boer, F.S. (eds.) TCS 2012. LNCS, vol. 7604, pp. 57–71. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33475-7_5 CrossRef

Chan, M.Y., Chin, F.Y.L.: General schedulers for the pinwheel problem based on double-integer reduction. IEEE Trans. Comput. 41(6), 755–768 (1992)CrossRef

Chan, M.Y., Chin, F.: Schedulers for larger classes of pinwheel instances. Algorithmica 9(5), 425–462 (1993)MathSciNetCrossRefMATH

Chuangpishit, H., Czyzowicz, J., Gasieniec, L., Georgiou, K., Jurdzinski, T., Kranakis, E.: Patrolling a path connecting set of points with unbalanced frequencies of visits (2012). http://arxiv.org/abs/1710.00466

Chrobak, M., Csirik, J., Imreh, C., Noga, J., Sgall, J., Woeginger, G.J.: The buffer minimization problem for multiprocessor scheduling with conflicts. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol. 2076, pp. 862–874. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-48224-5_70 CrossRef

10.

Collins, A., Czyzowicz, J., Gąsieniec, L., Kosowski, A., Kranakis, E., Krizanc, D., Martin, R., Morales Ponce, O.: Optimal patrolling of fragmented boundaries. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2013, New York, USA, pp. 241–250 (2013)

11.

Czyzowicz, J., Gąsieniec, L., Kosowski, A., Kranakis, E.: Boundary patrolling by mobile agents with distinct maximal speeds. In: Demetrescu, C., Halldórsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 701–712. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-23719-5_59 CrossRef

12.

Czyzowicz, J., Gasieniec, L., Kosowski, A., Kranakis, E., Krizanc, D., Taleb, N.: When patrolmen become corrupted: monitoring a graph using faulty mobile robots. In: Elbassioni, K., Makino, K. (eds.) ISAAC 2015. LNCS, vol. 9472, pp. 343–354. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48971-0_30 CrossRef

13.

Fishburn, P.C., Lagarias, J.C.: Pinwheel scheduling: achievable densities. Algorithmica 34(1), 14–38 (2002)MathSciNetCrossRefMATH

14.

Gąsieniec, L., Klasing, R., Levcopoulos, C., Lingas, A., Min, J., Radzik, T.: Bamboo garden trimming problem (perpetual maintenance of machines with different attendance urgency factors). In: Steffen, B., Baier, C., van den Brand, M., Eder, J., Hinchey, M., Margaria, T. (eds.) SOFSEM 2017. LNCS, vol. 10139, pp. 229–240. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-51963-0_18 CrossRef

15.

Holte, R., Mok, A., Rosier, L., Tulchinsky, I., Varvel, D.: The pinwheel: a real-time scheduling problem. In: II: Software Track, Proceedings of the Twenty-Second Annual Hawaii International Conference on System Sciences, vol. 2, pp. 693–702, January 1989

16.

Holte, R., Rosier, L., Tulchinsky, I., Varvel, D.: Pinwheel scheduling with two distinct numbers. Theoret. Comput. Sci. 100(1), 105–135 (1992)MathSciNetCrossRefMATH

17.

Kawamura, A., Kobayashi, Y.: Fence patrolling by mobile agents with distinct speeds. Distrib. Comput. 28(2), 147–154 (2015)MathSciNetCrossRefMATH

18.

Liang, D., Shen, H.: Point sweep coverage on path. Unpublished work https://arxiv.org/abs/1704.04332

19.

Lin, S.-S., Lin, K.-J.: A pinwheel scheduler for three distinct numbers with a tight schedulability bound. Algorithmica 19(4), 411–426 (1997)MathSciNetCrossRefMATH

20.

Ntafos, S.: On gallery watchmen in grids. Inf. Process. Lett. 23(2), 99–102 (1986)MathSciNetCrossRefMATH

21.

O’Rourke, J.: Art Gallery Theorems and Algorithms, vol. 57. Oxford University Press, Oxford (1987)MATH

22.

Romer, T.H., Rosier, L.E.: An algorithm reminiscent of Euclidean-gcd for computing a function related to pinwheel scheduling. Algorithmica 17(1), 1–10 (1997)MathSciNetCrossRefMATH

23.

Serafini, P., Ukovich, W.: A mathematical model for periodic scheduling problems. SIAM J. Discret. Math. 2(4), 550–581 (1989)MathSciNetCrossRefMATH

24.

Urrutia, J.: Art gallery and illumination problems. Handbook Comput. Geom. 1(1), 973–1027 (2000)MathSciNetCrossRefMATH

Titel: Patrolling a Path Connecting a Set of Points with Unbalanced Frequencies of Visits
verfasst von: Huda Chuangpishit
Jurek Czyzowicz
Leszek Gąsieniec
Konstantinos Georgiou
Tomasz Jurdziński
Evangelos Kranakis
Verlag: Springer International Publishing
Buch: SOFSEM 2018: Theory and Practice of Computer Science
Print ISBN: 978-3-319-73116-2

Electronic ISBN: 978-3-319-73117-9

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-73117-9_26

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"