情侣互相飞的 nested ticketing 问题

以前异地时想过多次往返另一个城市机票如何才能便宜。在网上找到了 back-to-back ticketing ，也叫 nested ticketing 的方法。这个方法是指购买两组往返机票，其中两段往返行程的部分停留时间重叠。这个在国内可能用处不大，但是美国用处还蛮大。和一些学生合作写了个文章研究这个问题的算法。

假如我们有一对异地情侣 A 和 B ，接下来 n 个周末都要团聚。我们知道所有的往返机票价格，怎么样才能最便宜的让他们团聚呢？

• A 更加愿意飞行，所以每次都是 A 飞去 B 那边。最便宜的买往返机票的方法可以规约为一个二分图最小权重匹配。
• 但是两边都可以飞对方那边，目标只是省最多的钱呢？这是 NP-hard 的。