2026 [ nach oben ]

de la Haye, Merlin; Lenzer, Pascal; Soheil, Farehe; Wunderlich, Marcus Metric Hedonic Games on the LineAAMAS 2026
[ BibTeX ] [ DOI ]
 
@article{delahaye2026metric, author = {de la Haye, Merlin and Lenzer, Pascal and Soheil, Farehe and Wunderlich, Marcus}, journal = {AAMAS}, keywords = {farehesoheil friedrich myown}, title = {Metric Hedonic Games on the Line}, year = 2026 }

Simonov, Kirill; Soheil, Farehe; Verma, Shaily Finding Minimum Distance Preservers: A Parameterized Studyarxiv 2026
[ BibTeX ] [ DOI ]
 
@article{simonov2026finding, author = {Simonov, Kirill and Soheil, Farehe and Verma, Shaily}, journal = {arxiv}, keywords = {farehesoheil friedrich myown}, title = {Finding Minimum Distance Preservers: A Parameterized Study}, year = 2026 }

2025 [ nach oben ]

Friedrich, Tobias; Simonov, Kirill; Soheil, Farehe Binary k-Center with Missing Entries: Structure leads to TractabilityIPEC 2025
[ BibTeX ] [ DOI ]
 
@article{friedrich2026binary, author = {Friedrich, Tobias and Simonov, Kirill and Soheil, Farehe}, journal = {IPEC}, keywords = {farehesoheil friedrich myown}, title = {Binary k-Center with Missing Entries: Structure leads to Tractability}, year = 2025 }

Döring, Michelle; Fehse, Jan; Friedrich, Tobias; Marten, Paula; Mohrin, Niklas; Simonov, Kirill; Soheil, Farehe; Timm, Jakob; Verma, Shaily Parameterized Complexity of Vehicle RoutingIPEC 2025
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
The Vehicle Routing Problem (VRP) is a popular generalization of the Traveling Salesperson Problem. Instead of one salesperson traversing the entire weighted, undirected graph G, there are k vehicles available to jointly cover the set of clients C subseteq V(G). Every vehicle must start at one of the depot vertices D subseteq V(G) and return to its start. Capacitated Vehicle Routing (CVRP) additionally restricts the route of each vehicle by limiting the number of clients it can cover, the distance it can travel, or both. In this work, we study the complexity of VRP and the three variants of CVRP for several parameterizations, in particular focusing on the treewidth of G. We present an FPT algorithm for VRP parameterized by treewidth. For CVRP, we prove paraNP- and W[cdot]-hardness for various parameterizations, including treewidth, thereby rendering the existence of FPT algorithms unlikely. In turn, we provide an XP algorithm for CVRP when parameterized by both treewidth and the vehicle capacity.
@article{döring_ParameterizedVehicleRouting_2025, abstract = {The Vehicle Routing Problem (VRP) is a popular generalization of the Traveling Salesperson Problem. Instead of one salesperson traversing the entire weighted, undirected graph G, there are k vehicles available to jointly cover the set of clients C \subseteq V(G). Every vehicle must start at one of the depot vertices D \subseteq V(G) and return to its start. Capacitated Vehicle Routing (CVRP) additionally restricts the route of each vehicle by limiting the number of clients it can cover, the distance it can travel, or both. In this work, we study the complexity of VRP and the three variants of CVRP for several parameterizations, in particular focusing on the treewidth of G. We present an FPT algorithm for VRP parameterized by treewidth. For CVRP, we prove paraNP- and W[\cdot]-hardness for various parameterizations, including treewidth, thereby rendering the existence of FPT algorithms unlikely. In turn, we provide an XP algorithm for CVRP when parameterized by both treewidth and the vehicle capacity.}, author = {Döring, Michelle and Fehse, Jan and Friedrich, Tobias and Marten, Paula and Mohrin, Niklas and Simonov, Kirill and Soheil, Farehe and Timm, Jakob and Verma, Shaily}, journal = {IPEC}, keywords = {IPEC farehesoheil ipec jakobtimm janfehse kirillsimonov masterproject michelledoering myown niklasmohrin parameterizedcomplexity paulamarten shaileyverma tobiasfriedrich travelingsalesperson vehiclerouting year2025}, title = {Parameterized Complexity of Vehicle Routing}, year = 2025 }

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 }