课题基金 / 基金详情

Online Network Optimization

Online Network Optimization
在线网络优化
批准号:
9209283
负责人:
Kirk Pruhs
金额:
$7.27万
依托单位:
依托单位国家:
美国
项目类别:
Continuing Grant
财政年份:
1992
资助国家:
美国
项目状态:
已结题
起止时间:
1992-06-15 至 1996-05-31

项目摘要

项目成果

Kirk Pruhs的其他基金

相似基金

相关文献

中文摘要
翻译
这项工作将研究经典网络优化问题的自然在线版本:最小生成树问题、最短路径问题、最小成本最大流问题、加权匹配问题和旅行推销员问题。在这些问题中,在线算法必须在所有底层网络已知之前开始构造部分解。因此,在线算法通常不可能知道一个特定的部分解是否会扩展到一个最优的全局解。这些问题的特点是,当网络的进一步信息已知时,重构部分解决方案是不切实际的,甚至是不可能的。因此,在线算法的目标是迭代地构造一个接近最优的解,而不需要从一个部分解到下一个部分解进行重大的重构。
英文摘要
This work will investigate natural online versions of the classical network optimization problems: the minimal spanning tree problem, the shortest path problem, the min-cost max-flow problem, the weighted matching problem, and the traveling salesman problem. In these problems an online algorithm must begin constructing a partial solution before all of the underlying network becomes known. Hence, it is generally not possible for the online algorithm to know whether a particular partial solution will extend to an optimal global solution. The hallmark of these problems is that it is impractical, or even impossible, to restructure the partial solution when further information about the network becomes known. The online algorithm's goal is thus to iteratively construct a solution that is close to optimal without significant restructuring from one partial solution to the next.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
AF: SMALL: Relational Algorithms
  • 批准号:
    2209654
  • 项目类别:
    Standard Grant
  • 资助金额:
    $25.08万
  • 财政年份:
    2022
  • 负责人:
    Kirk Pruhs
  • 依托单位:
EAGER: AF:Small: Algorithms for Relational Machine Learning
  • 批准号:
    2036077
  • 项目类别:
    Standard Grant
  • 资助金额:
    $14.88万
  • 财政年份:
    2020
  • 负责人:
    Kirk Pruhs
  • 依托单位:
AF:Small: Algorithmic Management of Heterogeneous Resources
  • 批准号:
    1907673
  • 项目类别:
    Standard Grant
  • 资助金额:
    $23.94万
  • 财政年份:
    2019
  • 负责人:
    Kirk Pruhs
  • 依托单位:
AitF: EXPL: Data Management in Domain Wall Memory-based Scratchpad for High Performance Mobile Devices
  • 批准号:
    1535755
  • 项目类别:
    Standard Grant
  • 资助金额:
    $39.99万
  • 财政年份:
    2015
  • 负责人:
    Kirk Pruhs
  • 依托单位:
国内基金
海外基金
XsmiR167为核心的ceRNA network调控文冠果雄花雌蕊败育机制研究
  • 批准号:
    32572006
  • 项目类别:
    面上项目
  • 资助金额:
    50.00万元
  • 批准年份:
    2025
  • 负责人:
    敖妍
  • 依托单位:
丝氨酸/甘氨酸/一碳代谢网络(SGOC metabolic network)调控炎症性巨噬细胞活化及脓毒症病理发生的机制研究
  • 批准号:
    81930042
  • 项目类别:
    重点项目
  • 资助金额:
    305.0万元
  • 批准年份:
    2019
  • 负责人:
    王迪
  • 依托单位:
多维在线跨语言Calling Network建模及其在可信国家电子税务软件中的实证应用
  • 批准号:
    91418205
  • 项目类别:
    重大研究计划
  • 资助金额:
    170.0万元
  • 批准年份:
    2014
  • 负责人:
    郑庆华
  • 依托单位:
基于Wireless Mesh Network的分布式操作系统研究
  • 批准号:
    60673142
  • 项目类别:
    面上项目
  • 资助金额:
    27.0万元
  • 批准年份:
    2006
  • 负责人:
    罗惠琼
  • 依托单位: