Publications with Juan José Besa Vial
- Scheduling autonomous vehicle platoons through an unregulated
intersection.
J. Besa, W. E. Devanny, D. Eppstein, and M. T. Goodrich.
Proc. 16th Worksh. Algorithmic Approaches for Transportation Modelling, Optimization and Systems (ATMOS 2016), Aarhus, Denmark, 2016.
OpenAccess Series in Informatics (OASIcs) 54, Schloss Dagstuhl (2016), pp. 5:1–5.16.
arXiv:1609.04512.
We consider a model of vehicle scheduling in which vehicles arrive at an intersection in indivisible platoons (or individual vehicles of variable length) and the goal is to find a schedule for them to all cross the intersection without collisions, minimizing the maximimum delay incurred by any platoon. We show that for many types of intersections, an optimal schedule can be found in polynomial time by a combination of dynamic programming and parametric search.
- Quadratic time algorithms appear to be optimal for sorting
evolving data.
J. Besa, W. E. Devanny, D. Eppstein, M. T. Goodrich, and T. Johnson.
Proc. Algorithm Engineering & Experiments (ALENEX 2018), New Orleans, 2018, pp. 87–96.
arXiv:1805.05443.We experiment with sorting algorithms in the evolving data model, in which, at the same time as the algorithm compares pairs of elements and possibly chooses a new ordering based on the results of the comparison, an adversary randomly chooses two adjacent elements in the sorted order and swaps them. As we show, bubble sort and its variants appear to maintain an order that is within inversion distance of optimal.
- Optimally sorting evolving data.
J. Besa, W. E. Devanny, D. Eppstein, M. T. Goodrich, and T. Johnson.
arXiv:1805.03350
Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague.
Leibniz International Proceedings in Informatics (LIPIcs) 107, pp. 81:1–81:13.
Suppose that a collection of objects has a linear order that is evolving by swaps of randomly chosen consecutive elements. We would like to maintain an approximation to this order using an algorithm that performs one comparison per swap. We show that repeated insertion sort can maintain linear inversion distance from the underlying order, the best possible.