2023 [ nach oben ]

Balig{{á}}cs, J{{ú}}lia; Disser, Yann; Soheil, Farehe; Weckbecker, David Tight Analysis of the Lazy Algorithm for Open Online Dial-a-RideWorkshop Algorithms and Data Structures (WADS) 2023: 43–64
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In the open online dial-a-ride problem, a single server has to deliver transportation requests appearing over time in some metric space, subject to minimizing the completion time. We improve on the best known upper bounds on the competitive ratio on general metric spaces and on the half-line, for both the preemptive and non-preemptive version of the problem. We achieve this by revisiting the algorithm Lazy recently suggested in [WAOA, 2022] and giving an improved and tight analysis. More precisely, we show that it has competitive ratio 2.457 on general metric spaces and 2.366 on the half-line. This is the first upper bound that beats known lower bounds of 2.5 for schedule-based algorithms as well as the natural Replan algorithm.
@inproceedings{DBLP:conf/wads/BaligacsDSW23, abstract = {In the open online dial-a-ride problem, a single server has to deliver transportation requests appearing over time in some metric space, subject to minimizing the completion time. We improve on the best known upper bounds on the competitive ratio on general metric spaces and on the half-line, for both the preemptive and non-preemptive version of the problem. We achieve this by revisiting the algorithm Lazy recently suggested in [WAOA, 2022] and giving an improved and tight analysis. More precisely, we show that it has competitive ratio 2.457 on general metric spaces and 2.366 on the half-line. This is the first upper bound that beats known lower bounds of 2.5 for schedule-based algorithms as well as the natural Replan algorithm.}, author = {Balig{{á}}cs, J{{ú}}lia and Disser, Yann and Soheil, Farehe and Weckbecker, David}, booktitle = {Workshop Algorithms and Data Structures (WADS)}, keywords = {farehesoheil year2023}, pages = {43–64}, title = {Tight Analysis of the Lazy Algorithm for Open Online Dial-a-Ride}, year = 2023 }

2021 [ nach oben ]

Tabatabaei, Azadeh; Soheil, Farehe; Aletaha, Mohammad; Ghodsi, Mohammad Integer Cow-path Problem and Simple Robot Street SearchCanadian Conference on Computational Geometry (CCCG) 2021: 388–398
[ Abstract ] [ BibTeX ] [ Download ]
 
In this paper, we revisit the well-known cow-path problem and introduce a new variation called Integer Cow- path Problem (ICP). In the general cow-path problem, w rays with one common end-point and a robot standing on the end-point are given. A target point is put along one of the rays and can be detected only then it is reached by the robot. The robot has to find the target by traversing the rays starting from the end-point. In the ICP, the robot is restricted to take an integer number of steps. The goal is to design a strategy for the robot to find the target such that the length of the traveled path is as small as possible. We present a randomized strategy that gives an upper bound on the competitive ratio for the ICP. Furthermore, as an application of this variation, we study the Simple Robot Street Search problem and give a randomized strategy that is inspired from the strategy for the ICP.
@inproceedings{DBLP:conf/cccg/TabatabaeiSAG21, abstract = {In this paper, we revisit the well-known cow-path problem and introduce a new variation called Integer Cow- path Problem (ICP). In the general cow-path problem, w rays with one common end-point and a robot standing on the end-point are given. A target point is put along one of the rays and can be detected only then it is reached by the robot. The robot has to find the target by traversing the rays starting from the end-point. In the ICP, the robot is restricted to take an integer number of steps. The goal is to design a strategy for the robot to find the target such that the length of the traveled path is as small as possible. We present a randomized strategy that gives an upper bound on the competitive ratio for the ICP. Furthermore, as an application of this variation, we study the Simple Robot Street Search problem and give a randomized strategy that is inspired from the strategy for the ICP.}, author = {Tabatabaei, Azadeh and Soheil, Farehe and Aletaha, Mohammad and Ghodsi, Mohammad}, booktitle = {Canadian Conference on Computational Geometry (CCCG)}, keywords = {farehesoheil year2021}, pages = {388–398}, title = {Integer Cow-path Problem and Simple Robot Street Search}, year = 2021 }