Titlebook: Algorithms and Data Structures; 18th International S Pat Morin,Subhash Suri Conference proceedings 2023 The Editor(s) (if applicable) and T

flutter

,Tight Analysis of the Lazy Algorithm for Open Online Dial-a-Ride,nimizing 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 . recently suggested in [WAOA, 2022] and givi

酷热

,Online TSP with Known Locations,rival times. We study both the open variant, in which the algorithm is not required to return to the origin when all the requests are served, as well as the closed variant, in which the algorithm has to return to the origin after serving all the requests. Our aim is to measure the impact of the extr

inclusive

,Socially Fair Matching: Exact and Approximation Algorithms,practical motivations. However, in many applications of optimization problems, a “solution” corresponds to real-life decisions that have major impact on humans belonging to diverse groups defined by attributes such as gender, race, or ethnicity. Due to this motivation, the notion of . has recently e

抚育

,A Parameterized Approximation Scheme for Generalized Partial Vertex Cover,ger ., and the goal is to cover the maximum number of edges possible by picking exactly . vertices. In this paper, we study a natural extension of Partial Vertex Cover to multiple color classes of the edges. In our problem, we are additionally given a partition of . into . color classes . and covera

Juvenile

anaphylaxis

,Tight Approximation Algorithms for Ordered Covering,e of elements. The vertex cover problem is an important special case where the subsets and elements are respectively vertices and edges of a given undirected graph. On the other hand, the . versions of both problems offer a different perspective - the objective is to find a linear ordering of the co

Forehead-Lift

Online Minimum Spanning Trees with Weight Predictions,r the weights of all edges. Then the actual weights arrive one at a time and an irrevocable decision must be made regarding whether or not the edge should be included into the spanning tree. In order to assess the quality of our algorithms, we define an appropriate error measure and analyze the perf

钢盔

,Compact Distance Oracles with Large Sensitivity and Low Stretch,most . edges of ., the oracle returns an estimate . of the distance . between . and . in the graph . such that ...For any positive integer . and any ., we present an .-DSO with sensitivity ., stretch ., space ., and an . query time..Prior to our work, there were only three known .-DSOs with subquadr

breadth

,Finding Diameter-Reducing Shortcuts in Trees,n two distinct vertices . and . of ., can answer queries reporting the cost of the edge (., .) in constant time. We want to augment . with . shortcuts in order to minimize the diameter of the resulting graph..For ., . time algorithms are known both for paths [Wang, CG 2018] and trees [Bilò, TCS 2022

Expiration

,Approximating the Smallest ,-Enclosing Geodesic Disc in a Simple Polygon, . vertices, . of which are reflex vertices. We refer to such a disc as a SKEG disc. We present an algorithm to compute a SKEG disc using higher-order geodesic Voronoi diagrams with worst-case time . ignoring polylogarithmic factors..We then present a 2-approximation algorithm that finds a geodesic