IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v18y2009i4d10.1007_s10878-009-9236-7.html
   My bibliography  Save this article

The robot cleans up

Author

Listed:
  • M. E. Messinger

    (Dalhousie University)

  • R. J. Nowakowski

    (Dalhousie University)

Abstract

Imagine a large building with many corridors. A robot cleans these corridors in a greedy fashion, the next corridor cleaned is always the dirtiest to which it is incident. We determine bounds on the minimum s(G) and maximum S(G) number of time steps (over all edge weightings) before every edge of a graph G has been cleaned. We show that Eulerian graphs have a self-stabilizing property that holds for any initial edge weighting: after the initial cleaning of all edges, all subsequent cleanings require s(G) time steps. Finally, we show the only self-stabilizing trees are a subset of the superstars.

Suggested Citation

  • M. E. Messinger & R. J. Nowakowski, 2009. "The robot cleans up," Journal of Combinatorial Optimization, Springer, vol. 18(4), pages 350-361, November.
    • Handle: RePEc:spr:jcomop:v:18:y:2009:i:4:d:10.1007_s10878-009-9236-7
    DOI: 10.1007/s10878-009-9236-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-009-9236-7
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-009-9236-7?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. H. A. Eiselt & Michel Gendreau & Gilbert Laporte, 1995. "Arc Routing Problems, Part I: The Chinese Postman Problem," Operations Research, INFORMS, vol. 43(2), pages 231-242, April.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Arbib, Claudio & Servilio, Mara & Archetti, Claudia & Speranza, M. Grazia, 2014. "The directed profitable location Rural Postman Problem," European Journal of Operational Research, Elsevier, vol. 236(3), pages 811-819.
    2. Akbari, Vahid & Salman, F. Sibel, 2017. "Multi-vehicle synchronized arc routing problem to restore post-disaster network connectivity," European Journal of Operational Research, Elsevier, vol. 257(2), pages 625-640.
    3. Barbara De Rosa & Gennaro Improta & Gianpaolo Ghiani & Roberto Musmanno, 2002. "The Arc Routing and Scheduling Problem with Transshipment," Transportation Science, INFORMS, vol. 36(3), pages 301-313, August.
    4. Ghiani, Gianpaolo & Improta, Gennaro, 2000. "An efficient transformation of the generalized vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 122(1), pages 11-17, April.
    5. Angel Corberán & Gustavo Mejía & José M. Sanchis, 2005. "New Results on the Mixed General Routing Problem," Operations Research, INFORMS, vol. 53(2), pages 363-376, April.
    6. Jesica Armas & Peter Keenan & Angel A. Juan & Seán McGarraghy, 2019. "Solving large-scale time capacitated arc routing problems: from real-time heuristics to metaheuristics," Annals of Operations Research, Springer, vol. 273(1), pages 135-162, February.
    7. Chefi Triki, 2017. "Solving the Periodic Edge Routing Problem in the Municipal Waste Collection," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 34(03), pages 1-13, June.
    8. Luc Muyldermans & Patrick Beullens & Dirk Cattrysse & Dirk Van Oudheusden, 2005. "Exploring Variants of 2-Opt and 3-Opt for the General Routing Problem," Operations Research, INFORMS, vol. 53(6), pages 982-995, December.
    9. Fung, Richard Y.K. & Liu, Ran & Jiang, Zhibin, 2013. "A memetic algorithm for the open capacitated arc routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 50(C), pages 53-67.
    10. Yuhui Sun & Wei Yu & Zhaohui Liu, 2023. "Approximation algorithms for some min–max and minimum stacker crane cover problems," Journal of Combinatorial Optimization, Springer, vol. 45(1), pages 1-25, January.
    11. Li, Jiliu & Qin, Hu & Shen, Huaxiao & Tsui, Kwok Leung, 2019. "The unilateral transportation problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 132(C), pages 1-29.
    12. Buu-Chau Truong & Kim-Hung Pho & Van-Buol Nguyen & Bui Anh Tuan & Wing-Keung Wong, 2019. "Graph Theory And Environmental Algorithmic Solutions To Assign Vehicles Application To Garbage Collection In Vietnam," Advances in Decision Sciences, Asia University, Taiwan, vol. 23(3), pages 1-35, September.
    13. Sahin, Halenur & Kara, Bahar Yetis & Karasan, Oya Ekin, 2016. "Debris removal during disaster response: A case for Turkey," Socio-Economic Planning Sciences, Elsevier, vol. 53(C), pages 49-59.
    14. Muyldermans, L. & Cattrysse, D. & Van Oudheusden, D. & Lotan, T., 2002. "Districting for salt spreading operations," European Journal of Operational Research, Elsevier, vol. 139(3), pages 521-532, June.
    15. Jinghao Sun & Yakun Meng & Guozhen Tan, 2015. "An integer programming approach for the Chinese postman problem with time-dependent travel time," Journal of Combinatorial Optimization, Springer, vol. 29(3), pages 565-588, April.
    16. Gilbert Laporte & Roberto Musmanno & Francesca Vocaturo, 2010. "An Adaptive Large Neighbourhood Search Heuristic for the Capacitated Arc-Routing Problem with Stochastic Demands," Transportation Science, INFORMS, vol. 44(1), pages 125-135, February.
    17. Letchford, Adam N., 1999. "The general routing polyhedron: A unifying framework," European Journal of Operational Research, Elsevier, vol. 112(1), pages 122-133, January.
    18. Elena Fernández & Oscar Meza & Robert Garfinkel & Maruja Ortega, 2003. "On the Undirected Rural Postman Problem: Tight Bounds Based on a New Formulation," Operations Research, INFORMS, vol. 51(2), pages 281-291, April.
    19. Tagmouti, Mariam & Gendreau, Michel & Potvin, Jean-Yves, 2007. "Arc routing problems with time-dependent service costs," European Journal of Operational Research, Elsevier, vol. 181(1), pages 30-39, August.
    20. Beullens, Patrick & Muyldermans, Luc & Cattrysse, Dirk & Van Oudheusden, Dirk, 2003. "A guided local search heuristic for the capacitated arc routing problem," European Journal of Operational Research, Elsevier, vol. 147(3), pages 629-643, June.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:18:y:2009:i:4:d:10.1007_s10878-009-9236-7. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.