{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:52:41Z","timestamp":1753894361015,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","issue":"Discrete Algorithms","license":[{"start":{"date-parts":[[2025,2,16]],"date-time":"2025-02-16T00:00:00Z","timestamp":1739664000000},"content-version":"am","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,2,16]],"date-time":"2025-02-16T00:00:00Z","timestamp":1739664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,2,16]],"date-time":"2025-02-16T00:00:00Z","timestamp":1739664000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"accepted":{"date-parts":[[2025,2,16]]},"abstract":"<jats:p>We study a primitive vehicle routing-type problem in which a fleet of $n$unit speed robots start from a point within a non-obtuse triangle $\\Delta$, where $n \\in \\{1,2,3\\}$. The goal is to design robots' trajectories so as to visit all edges of the triangle with the smallest visitation time makespan. We begin our study by introducing a framework for subdividing $\\Delta$into regions with respect to the type of optimal trajectory that each point $P$ admits, pertaining to the order that edges are visited and to how the cost of the minimum makespan $R_n(P)$ is determined, for $n\\in \\{1,2,3\\}$. These subdivisions are the starting points for our main result, which is to study makespan trade-offs with respect to the size of the fleet. In particular, we define $ R_{n,m} (\\Delta)= \\max_{P \\in \\Delta} R_n(P)\/R_m(P)$, and we prove that, over all non-obtuse triangles $\\Delta$: (i) $R_{1,3}(\\Delta)$ ranges from $\\sqrt{10}$ to $4$, (ii) $R_{2,3}(\\Delta)$ ranges from $\\sqrt{2}$ to $2$, and (iii) $R_{1,2}(\\Delta)$ ranges from $5\/2$ to $3$. In every case, we pinpoint the starting points within every triangle $\\Delta$ that maximize $R_{n,m} (\\Delta)$, as well as we identify the triangles that determine all $\\inf_\\Delta R_{n,m}(\\Delta)$ and $\\sup_\\Delta R_{n,m}(\\Delta)$ over the set of non-obtuse triangles.<\/jats:p><jats:p>Comment: 47 pages, 27 figures<\/jats:p>","DOI":"10.46298\/dmtcs.8729","type":"journal-article","created":{"date-parts":[[2025,2,16]],"date-time":"2025-02-16T06:50:06Z","timestamp":1739688606000},"source":"Crossref","is-referenced-by-count":0,"title":["Makespan Trade-offs for Visiting Triangle Edges"],"prefix":"10.46298","volume":"vol. 26:3","author":[{"given":"Konstantinos","family":"Georgiou","sequence":"first","affiliation":[]},{"given":"Somnath","family":"Kundu","sequence":"additional","affiliation":[]},{"given":"Pawel","family":"Pralat","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2025,2,16]]},"container-title":["Discrete Mathematics &amp; Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dmtcs.episciences.org\/14965\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dmtcs.episciences.org\/14965\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,16]],"date-time":"2025-02-16T06:50:06Z","timestamp":1739688606000},"score":1,"resource":{"primary":{"URL":"https:\/\/dmtcs.episciences.org\/8729"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,16]]},"references-count":0,"journal-issue":{"issue":"Discrete Algorithms","published-online":{"date-parts":[[2025,2,16]]}},"URL":"https:\/\/doi.org\/10.46298\/dmtcs.8729","relation":{"has-preprint":[{"id-type":"arxiv","id":"2105.01191v2","asserted-by":"subject"},{"id-type":"arxiv","id":"2105.01191v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2105.01191","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2105.01191","asserted-by":"subject"}]},"ISSN":["1365-8050"],"issn-type":[{"type":"electronic","value":"1365-8050"}],"subject":[],"published":{"date-parts":[[2025,2,16]]},"article-number":"8729"}}