Online Assignment of Reservations to Parking Lots for Smart Cities under the i.i.d. Model

We consider the problem of assigning vehicles to parking lots under the i.i.d. (independent and identically distributed) model, a user arrives online and makes a reservation for a parking lot by specifying a date and time, and the system assigns a parking lot for that reservation in such a way as to minimize the standby time for the user to enter the parking lot and walking time between assigned parking lot of user and user’s destination. In this paper, we consider the variant of the problem first which ignores walking time (we will take walking time into account in future studies) , in this problem, we extend the work of Mehta et al.[FOCS 2005] to formulate this variant as an Adword Allocation Problem and found that the greedy algorithm can achieve a competitive ratio of $1 - \frac{1}{e}$ under i.i.d. model, in order to complete the whole system in the future, we also make a mathematical analysis of the performance guarantee of greedy algorithm in this variant first and our proof is very detailed.