权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Efficient Algorithms for Multiple Instance Network Flow and Cut Problems

针对多实例网络流量和切割问题的高效算法

基本信息

批准号：
9103937
负责人：
Daniel Gusfield
金额：
$ 8.71万
依托单位：
University of California-Davis
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
1991
资助国家：
美国
起止时间：
1991-08-15 至 1995-01-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=9103937&HistoricalAwards=false
关键词：
Efficient Algorithms Multiple Instance Network

项目摘要

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.

该项目将重点关注多实例组合优化问题，特别是两类多实例网络流和割问题，以及通过此类多实例计算解决的组合问题。许多重要的组合问题是通过解决一系列网络流或最小割问题来解决的，其中每个连续的问题实例都以高度结构化的方式与其前一个问题实例不同。问题实例的相似性使得解决序列比独立解决每个实例更有效。该项目将集中研究通过改变源节点和汇节点的选择或系统地改变边缘容量而产生的多实例网络流和最小割问题。解决这些问题的一个重要方法是理解序列中可能遇到的所有问题实例的空间的解决方案集的结构，并使用这种结构理解以某种紧凑的隐式形式有效地表示所有潜在实例的解决方案集。然后，一旦指定了特定实例，就可以比从头开始求解实例更快地从表示中扩展和检索它。因此，该项目的很大一部分旨在发展这种结构理解和紧凑的表示。