Seat reservation in case of all reservations could be placed by an optimal strategy
Using the application
Reservations can be added as well as deleted. The added reservations can be reserved - step by step - according to the chosen strategy.
Users guide:
Click Settings to adjust number of seats and number of stations
Click Reserve to reserve the next reservation request
Click Cancel to cancel the seat number assignment of the last reservation
Click Remove to delete the last reservation request
Click Add to add a new reservation request. Numbers of start- and endstation must be typed into the corresponding textfields
Choose between 3 Views. Look at the whole scedule or select one specific seat or station
Click Unit Cost to load a scenario which demonstrates the upper bound of the Unit Cost Model
Click Proportional Cost to load a scenario which demonstrates the upper bound of the Proportional Cost Model
At first all reservation request should be added. Then they can be reserved one by one and the assigning process can be seen
The strategy can be changed at any time. The reservation requests become reassigned automatically.
Seat Reservation Application
Here you can start the application.
Evaluation of strategies
Strategies try to assign seats in a way that the income from selling the tickets is maximized.
The upper bounds for the strategies can be achieved by setting up worst case scenarios. The bounds on the accommodating ratios can be observed at any time when reserving reservations.
Two cost models are implemented:
Unit Cost Model: Every trip has cost of 1 unit
Proportional Cost Model: The cost of a trip is porportional to its length
The Accommodating Ratio of a fair strategy given a sequence of reservation requests is
The earn of the strategy divided by the earn of the optimal strategy.
Accommodating means that the optimal strategy can accommodate all reservation requests. Fair means that the strategy must not reject a reservation request to wich it could a seatnumber.
Lower bounds are valid in all scenarios, upper bounds only in special scenarios. Our aim is to
proove large lower bounds
give examples with small lower bounds
The current accommodating ratio in the Unit Cost Model and the Proportional Cost Model are always up to date.
The following strategies are available:
First Fit: Every reservation request is placed on the first seat that can accommodate the whole reservation request
Best Fit: Every reservation request is placed on the seat wich leaves the smallest gap. A gap is an consecutive number of station before and after the journey where every seat is free.
Random: From all possible seats one is chosen arbitrarily.
Results
In the following section let the number of stations be k.
Unit Cost Model
Universal bounds
Lower bound:
Theorem Any fair strategy for the seat reservation problem is 1/2 - accommodating
Upper bound:
Theorem No fair strategy for the seat reservation problem is more than 6/7 - accommodating, when k ≥ 4
First Fit
Upper bound:
Theorem First Fit is no better than (2k-2)/(3k-6) - accommodating, when k ≥ 7 and k = 1 (mod 3)
Best Fit
Upper bound:
Theorem Best Fit is no better than (2k-2)/(3k-6) - accommodating, when k ≥ 7 and k = 1 (mod 3)
Proportional Cost Model
Universal bounds
Lower bound:
Theorem Any fair strategy for the seat reservation problem is 1/(k - 1) - accommodating
Upper bound:
Theorem No fair strategy for the seat reservation problem is more than 11,211/(10,211+k) - accommodating, when k ≥ 4
First Fit
Upper bound:
Theorem First Fit is no better than 4/(k+2) - accommodating.
Best Fit
Obere Schranke:
Theorem Best Fit is no better than 4/(k+2) - accommodating.
