{"entities":{"Q405281":{"pageid":407048,"ns":120,"title":"Item:Q405281","lastrevid":56884488,"modified":"2026-03-24T10:44:35Z","type":"item","id":"Q405281","labels":{"en":{"language":"en","value":"On fence patrolling by mobile agents"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6340228"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405281$93D2BAB6-3A39-452E-820E-36AC7CCC41E7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a482d9937f36e9a134363bd7bef9031604e54113","datavalue":{"value":{"text":"On fence patrolling by mobile agents","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q405281$7B2037C3-9F3B-49F2-A1BC-1D6EFF32307C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"68d8ca55eb429904e3c5e61bcc010b2aad14121b","datavalue":{"value":"1307.90149","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405281$0647B105-282F-4468-BF38-F65EB6E1F6C3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e5b905a1f97eedf9f0c58cb4ee92d3415099d061","datavalue":{"value":{"entity-type":"item","numeric-id":202655,"id":"Q202655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405281$F0BCA405-228E-430B-A535-703656E739D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cf82bada7f3be5e4ee74d921c4067f089a3d7bec","datavalue":{"value":{"entity-type":"item","numeric-id":405280,"id":"Q405280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405281$B2E04CE8-255B-4B1A-836A-D83580F4AC09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3a988ad1020b4a6ab1082581edf26c8f03761c8a","datavalue":{"value":{"entity-type":"item","numeric-id":344783,"id":"Q344783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405281$4303B893-8954-4842-A6FC-324F66F62724","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405281$C5BE1FCC-864E-40BD-8CEB-C2680D3FF9A8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f9d8fea32a46af1bd8128cc5dcfc32073a3817d0","datavalue":{"value":{"time":"+2014-09-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q405281$8FA71BD2-2A53-4369-9182-A4AD7951C7BC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"682c3efe92959fc4775c958e4f5cb440edd8e433","datavalue":{"value":"https://arxiv.org/abs/1401.6070","type":"string"},"datatype":"url"},"type":"statement","id":"Q405281$445AEC89-B430-470B-B6A1-6744722DC51A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"ea3ed1d376bbb055382ad6ac3b71625e3a57c5a7","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/4063","type":"string"},"datatype":"url"},"type":"statement","id":"Q405281$5E7AD466-A029-40BF-B303-55B417D9496B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"51002bea588a9d3deb1aaf686792fd83ad7a5822","datavalue":{"value":"Summary: Suppose that a fence needs to be protected (perpetually) by \\(k\\) mobile agents with maximum speeds \\(v_1,\\dots,v_k\\) so that no point on the fence is left unattended for more than a given amount of time. The problem is to determine if this requirement can be met, and if so, to design a suitable patrolling schedule for the agents. Alternatively, one would like to find a schedule that minimizes the \\textit{idle time}, that is, the longest time interval during which some point is not visited by any agent. We revisit this problem, introduced by \\textit{J. Czyzowicz} et al. [ESA 2012, Lect. Notes Comput. Sci. 6942, 701--712 (2011; Zbl 1260.68397)], and discuss several strategies for the cases where the fence is an open and a closed curve, respectively.{  } In particular: (i) we disprove a conjecture by Czyzowicz et al. (loc. cit.) regarding the optimality of their algorithm \\({\\mathcal A}_2\\) for unidirectional patrolling of a closed fence; (ii) we present a schedule with a lower idle time for patrolling~an open fence, improving an earlier result of \\textit{A. Kawamura} and \\textit{Y. Kobayashi} [ISAAC 2012, Lect. Notes Comput. Sci. 7676, 598--608 (2012; Zbl 1260.90141)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q405281$64EE3EED-D51A-4E39-810D-BE98D816CD60","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405281$A806E484-B509-49AD-90D8-BE81007917CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405281$8FB587C1-148D-46CB-8F52-95305BADFF79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"709ed67c42bb169499eabe0b6d04c203d4526e03","datavalue":{"value":"68T42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405281$7882F841-4415-46FD-BD81-C7BB6C44E81F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405281$7850949B-AB5B-4E5D-B5AF-C7FA2513F2D0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"890a655be9a6c930adb1315fc6734426ba8a730e","datavalue":{"value":"6340228","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405281$DB46BA8A-4875-46EC-AAA5-C419BC7B1525","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a61fa3e2944ea89ff39ae7648f87b5a9f1837f14","datavalue":{"value":"multi-agent patrolling","type":"string"},"datatype":"string"},"type":"statement","id":"Q405281$98595378-F54E-4D8B-9A64-71810A0431A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a763b5531919da026d32c97699f82cbfa8d116b1","datavalue":{"value":"idle time","type":"string"},"datatype":"string"},"type":"statement","id":"Q405281$A7888E31-A4E5-4032-B446-8D69433D4E03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q405281$2F6FBA9B-F9B0-459E-8666-C2F9C7D7D6B7","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405281$95EF8427-4CBA-4222-8915-349A5592879C","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"932ba94896d2ce7be94760cc25dcf2b7084cd5d8","datavalue":{"value":"bafkreifh3bxkvmwwumkaqojurbs2eeka2pranqjk2omllnzuzr53dpxe2a","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405281$EE3871B1-B7B7-42CF-BF21-6A8189E1CBF1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0248c8d8fc871e39849bc19c24b4782eafa80898","datavalue":{"value":{"entity-type":"item","numeric-id":2947025,"id":"Q2947025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c4840d39bdf2efe3b8c265204f1d28147e582e1","datavalue":{"value":{"amount":"+0.8908790946006775","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q405281$9A51E7E6-9F19-49AA-A98C-49798AE3044C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"87abda4f7df0216348d08726761ee255bf997ab6","datavalue":{"value":{"entity-type":"item","numeric-id":2196578,"id":"Q2196578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3aeb70f8cf7a73d772c2fde69b03eaf88ffb4310","datavalue":{"value":{"amount":"+0.885054349899292","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q405281$D4220FB4-D3AE-4265-B141-707D60BFE070","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78c02a23f81ecccd6f613a57f1e8dc1630c3e76e","datavalue":{"value":{"entity-type":"item","numeric-id":3092272,"id":"Q3092272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95e5bbd29d348a29baebecb0d2f3a29dc845f45a","datavalue":{"value":{"amount":"+0.8362607955932617","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q405281$CEBFD722-AAFF-4DC2-8845-6B2D381C1F82","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:405281","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:405281"}}}}}