2023/07/17 by Arndt, Stephen, Josh Ascher, Kirk Pruhs +2 · 1 citation
Engineering · Computer Science · #Smart Parking Systems Research #Optimization and Search Problems #Transportation and Mobility Innovations
paper · pdf · doi:10.48550/arxiv.2307.08832
We consider the online transportation problem set in a metric space containing parking garages of various capacities. Cars arrive over time, and must be assigned to an unfull parking garage upon their arrival. The objective is to minimize the aggregate distance that cars have to travel to their assigned parking garage. We show that the natural greedy algorithm, augmented with garages of k≥3 times the capacity, is (1 + (2)/(k-2))-competitive.