共计 293 个字符，预计需要花费 1 分钟才能阅读完成。
以前异地时想过多次往返另一个城市机票如何才能便宜。在网上找到了 back-to-back ticketing，也叫 nested ticketing 的方法。这个方法是指购买两组往返机票，其中两段往返行程的部分停留时间重叠。这个在国内可能用处不大，但是美国用处还蛮大。 和一些学生合作写了个文章研究这个问题的算法 。
假如我们有一对异地情侣 A 和 B，接下来 n 个周末都要团聚。我们知道所有的往返机票价格，怎么样才能最便宜的让他们团聚呢？
- A 更加愿意飞行，所以每次都是 A 飞去 B 那边。最便宜的买往返机票的方法可以规约为一个二分图最小权重匹配。
- 但是两边都可以飞对方那边，目标只是省最多的钱呢？这是 NP-hard 的。
正文完
