Processing math: 31%

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 nunit speed robots start from a point within a non-obtuse triangle Δ, where n{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 Δ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 Rn(P) is determined, for n{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 Rn,m(Δ)=max, 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 104 times.
    This article's PDF has been downloaded 33 times.