## Assign seats of a train to passengers

We present the following application:
• 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

[Application cannot run]
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.
• Authors: Simone Lehmann, Rainer Penninger

Bibliography:

 [1]: Joan Bojar, Kim S. Larsen. Paper on the Seat Reservation Problem.