Efficient Algorithms for Multiple Instance Combinatorial Problems

本项目将主要关注多实例网络流量计算问题。许多重要的、非平凡的组合问题可以转化为一系列密切相关的网络流计算来求解。最近的结果提高了计算这类序列的效率，反过来也导致了重要组合问题的更快解决。这个项目将扩展最近的工作，集中在特定重要组合问题的一般方法上。具体地，将假设两类一般的序列：参数网络流问题，其中通过改变某些边的容量来生成序列；以及多源-汇聚问题，其中通过改变源节点和汇节点的选择来生成序列。

This project will focus largely on problems of multiple instance network flow computations. Many important, non-trivial combinatorial problems can be cast and solved as a sequence of closely related network flow computations. Recent results have led to improved efficiency in computing such sequences, and in turn this has lead to faster solutions to important combinatorial problems. This project will extend recent work, concentrating on general methods to specific important combinatorial problems. In particular, two general classes of sequence will be assumed: parametric network flow problems, where the sequence is generated by changing the capacities of certain edges, and multiple source-sink problems, where the sequence are generated by changing the choices of source and sink nodes.