Efficient Algorithms for Multiple Instance Network Flow and Cut Problems

这个项目将集中在多实例组合的问题 优化，特别是两种类型的多实例网络流 切割问题和组合问题， 多实例计算。 许多非平凡组合 通过求解网络流或最小值序列来解决问题。 切割问题，其中每个连续的问题实例与其 以一种高度结构化的方式。 问题的相似性 实例可以更有效地解决序列， 通过独立地解决每个实例。 该项目将 集中于多实例网络流和最小割 这些问题是由改变来源的选择而产生的， 和汇聚节点，或者通过系统地改变边缘容量。 一个 解决这些问题的一个重要方法是了解 所有问题实例空间的解决方案集， 在序列中遇到，并使用此结构 理解有效地表示，在一些紧凑的隐式形式， 所有潜在实例的解决方案集。 然后一旦A 如果指定了一个特定实例，则可以展开和检索该实例 比从表示中求解实例更快， 抓痒.你知道 因此，该项目的很大一部分是针对 发展这样的结构理解和紧凑的表示。

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.