Efficient Algorithms for Multiple Instance Network Flow and Cut Problems

点击翻译按钮获取中文摘要

This project will focus on problems of multiple instance combinatorial optimization, particularly two types of multiple instance network flow and cut problems, and combinatorial problems that are solved by such multiple instance computations. Many non-trivial combinatorial problems are solved by solving a sequence of network flow or minimum cut problems, where each successive problem instance differs from its predecessor in a highly structured way. The similarity of the problem instances allows the sequence to be solved much more efficiently than by solving each instance independently. This project will concentrate on multiple instance network flow and minimum cut problems that are generated either by changing the choice of source and sink nodes, or by systematically changing edge capacities. An important approach to these problems is to understand the structure of the set of solutions to the space of all problem instances that might be encountered in the sequence, and to use this structural understanding to efficiently represent, in some compact implicit form, the set of solutions to all potential instances. Then once a particular instance is specified, it can be expanded and retrieved from the representation faster than by solving the instance from scratch. Hence a large part of the project is directed towards developing such structural understanding and compact representations.