Konstantinos Georgiou ; Somnath Kundu ; Pawel Pralat - Makespan Trade-offs for Visiting Triangle Edges

dmtcs:8729 - Discrete Mathematics & Theoretical Computer Science, February 16, 2025, vol. 26:3 - https://doi.org/10.46298/dmtcs.8729
Makespan Trade-offs for Visiting Triangle EdgesArticle

Authors: Konstantinos Georgiou ; Somnath Kundu ; Pawel Pralat

    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.


    Volume: vol. 26:3
    Section: Discrete Algorithms
    Published on: February 16, 2025
    Accepted on: December 10, 2024
    Submitted on: November 19, 2021
    Keywords: Computer Science - Discrete Mathematics

    Consultation statistics

    This page has been seen 77 times.
    This article's PDF has been downloaded 26 times.