## 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

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

**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.__

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

*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

**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

**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. |