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.