The Art Gallery Guardian

An algorithm for covert back-to-back ticketing

Airline booking ploys are ways to circumventing airlines ticket rules in order to spend less on the ticket. We consider a special case, the back-to-back ticketing/nested ticketing. TripSavvy has a good article on back-to-back ticketing.

For many airlines, back-to-back ticketing is explicitly forbidden, this includes American Airlines, Delta and United.

We want to model back-to-back ticketing into an algorithmic problem. There is a sequence of trips between two locations, and it can be grouped into different round trips. Each round trip itinerary has a different cost. A round trip itinerary is no more than a matching between two trips.

This can be seen as simple matching problem. The vertices are trips, which we can assume a trip means “traveling from A to B on date x”. There is an edge between two trips, if there is a round trip itinerary containing the trips. The cost of the edge is the cost of buying a round trip for those two trips. Since it is also possible that we buy a one-way ticket, there are also self-loops. Also, we can consider a multigraph, where the edges are colored. Each color class represents an airline.

If one does not care about the airline finding out, it is just a minimum weight perfect matching problem allowing self-loops. However, people might actually care about airline not happy about this practice. Hence we are interested in making sure in each airline, we have no overlapping itineraries. However, we do allow overlapping itineraries across airlines.

For two edges {a,b}\set{a,b} and {c,d}\set{c,d} defined over integers, it is independent if [a,b][c,d]=[a,b]\cap [c,d]= \emptyset. A set of edges is independent if the edges are pairwise independent.

Problem1Covert back-to-back ticketing problem

Input: A multigraph G=(V,E)G=(V,E) where V[n]V\subseteq [n], each edge can be one of kk colors, and there is an edge cost function c:ER+c:E\to \R^+.

Output: A perfect matching MM (allowing self-loops), such that each color class of MM is independent, and the cost is minimized.

I suspect for arbitrary kk, the problem is NP-hard. We show how to solve the problem in polynomial time for k=2k=2.

Yizhi Song stated the idea that if one edge in a color is picked, it forces some edges of the other color to be picked. We can use the idea to obtain an O(n3)O(n^3) time algorithm for this problem.

Since we are only working with k=2k=2 case, we will let aˉ\bar{a} to be the color that is not aa. Recall [n]={1,,n}[n]=\set{1,\ldots,n} and [a..b]={a,a+1,,b}[a..b] = \set{a,a+1,\ldots,b}. We assume the vertices V=[n]V=[n]. For a graph with kk color classes, we define GaG_a to be the subgraph consists of all edges of color aa. ca(x,y)c_a(x,y) is the cost of a color aa edge xyxy. We define D(a,y,z)D(a,y,z) as the optimal solution when the input graph is Gaˉ[[z1]{y}]Ga[[y1]]G_{\bar{a}}[[z-1]\setminus \set{y}] \cup G_a[[y-1]]. Intuitively, this is the optimal solution where we need to match all vertices in Z=[z1]{y}Z = [z-1] \setminus \set{y}, but can only use aa colored that is fully contained in [y1][y-1], and aˉ\bar{a} colored edges fully contained ZZ. We also define Ca(x,y)C_{a}(x,y) to be the optimal solution when the input graph is Ga[[x..y]]G_a[[x..y]]. Namely, a min-cost perfect matching covering all vertices [x..y][x..y] but we can only use aa colored edges contained in [x..y][x..y].

The optimal solution is D(a,n+1,n+1)D(a,n+1,n+1) for either color aa.

We express the recursive relation. For y<zy<z, we have the following. D(a,y,z)=min{minx<y{Caˉ(y+2,z1)+caˉ(x,y+1)+D(aˉ,x,y)}Caˉ(y+1,z1)+D(aˉ,y,y) D(a,y,z) =\min \begin{cases} \min_{x<y} \set{ C_{\bar{a}}(y+2,z-1) + c_{\bar{a}}(x,y+1) + D(\bar{a},x,y)}\\ C_{\bar{a}}(y+1,z-1) + D(\bar{a},y,y) \end{cases} It might be beneficial to see the intuition behind the two cases through the following pictures.

First case.
Second case.

On the other hand, when y=zy=z D(a,y,y)=minx<y{D(a,x,y)+ca(x,y),D(aˉ,x,y)+caˉ(x,y)} D(a,y,y) =\min_{x<y} \set{ D(a,x,y) + c_a(x,y), D(\bar{a},x,y) + c_{\bar{a}}(x,y)} One can easily infer the base case through definition. Note that all values of CaC_a can be computed in O(n2)O(n^2) time. It takes O(n)O(n) time to compute one value in DD. Therefore, the total running time is O(n3)O(n^3).

One can show that even with kk different airlines, there is an algorithm with running time O(nO(k))O(n^{O(k)}).

Posted by Chao Xu on .
Tags: Optimization, algorithm, airline.