AF: Medium: Collaborative Research: Solutions to Planar Optimization Problems

AF:中:协作研究:平面优化问题的解决方案

基本信息

  • 批准号:
    0963921
  • 负责人:
  • 金额:
    $ 17.5万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2010
  • 资助国家:
    美国
  • 起止时间:
    2010-08-01 至 2014-07-31
  • 项目状态:
    已结题

项目摘要

The aim of this research is to develop new algorithms and algorithmictechniques for solving fundamental optimization problems on planarnetworks. Many optimization problems in networks are consideredcomputationally difficult; some are even difficult to solveapproximately. However, problems often become easier when the inputnetwork is restricted to be planar, i.e. when it can be drawn on theplane so that no edges cross each other. Such planar instances ofoptimization problems arise in several application areas, includinglogistics and route planning in road maps, image processing andcomputer vision, and VLSI chip design.The investigators plan to develop algorithms that achieve fasterrunning times or better approximations by exploiting the planarity ofthe input networks. In addition, in order to address the use ofoptimization in the discovery of some ground truth, the investigatorswill develop algorithms not just for the traditional worst-case inputmodel but also for models in which there is an unusually good plantedsolution; for a model of this kind, the investigators expect to findalgorithms that produce even more accurate answers.The research will likely uncover new computational techniques whoseapplicability goes beyond planar networks. In the recent past, once atechnique has been developed and understood in the context of planarnetworks, it has been generalized to apply to broader families ofnetworks.In addition, new algorithms and techniques resulting from thisresearch might enable people to quickly compute better solutions toproblems arising in diverse application areas. For example, researchin this area has already had an impact in the computer visioncommunity. Further research has the potential to be useful, forexample, in the design of networks, the planning of routes in roadmaps, the processing of images.
本研究的目的是开发新的算法和算法技术来解决平面网络上的基本优化问题。网络中的许多优化问题被认为是计算困难的,有些甚至难以近似求解。然而,当输入网络被限制为平面时,问题往往变得更容易,即当它可以在平面上绘制时,没有边相互交叉。这种平面优化问题的例子出现在几个应用领域,包括物流和路线规划的路线图,图像处理和计算机视觉,以及超大规模集成电路芯片设计。研究人员计划开发算法,通过利用输入网络的平面性,实现更快的运行时间或更好的近似。此外,为了解决在发现某些基本事实时使用优化的问题,建模者不仅要为传统的最坏情况输入模型开发算法,还要为存在异常好的种植解决方案的模型开发算法;对于这种类型的模型,研究人员希望找到能产生更准确答案的算法。这项研究可能会发现适用性更广的新计算技术平面网络近年来,一旦一项技术在平面网络的背景下得到发展和理解,它就被推广应用到更广泛的网络家族中。此外,这项研究产生的新算法和技术可能使人们能够快速计算出更好的解决方案,以解决各种应用领域中出现的问题。例如,这一领域的研究已经在计算机视觉界产生了影响。进一步的研究有可能是有用的,例如,在网络的设计,路线图中的路线规划,图像处理。

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Glencora Borradaile其他文献

The knapsack problem with neighbour constraints
  • DOI:
    10.1016/j.jda.2012.04.011
  • 发表时间:
    2012-10-01
  • 期刊:
  • 影响因子:
  • 作者:
    Glencora Borradaile;Brent Heeringa;Gordon Wilfong
  • 通讯作者:
    Gordon Wilfong
Safe and tight linear estimators for global optimization
  • DOI:
    10.1007/s10107-004-0533-8
  • 发表时间:
    2004-07-07
  • 期刊:
  • 影响因子:
    2.500
  • 作者:
    Glencora Borradaile;Pascal Van Hentenryck
  • 通讯作者:
    Pascal Van Hentenryck

Glencora Borradaile的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Glencora Borradaile', 18)}}的其他基金

AF: Small: Collaborative Research: Efficient Algorithms for Cycles on Surfaces
AF:小型:协作研究:表面循环的高效算法
  • 批准号:
    1617951
  • 财政年份:
    2016
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Standard Grant
CAREER: Understanding and advancing network design in planar domains
职业:理解和推进平面域中的网络设计
  • 批准号:
    1252833
  • 财政年份:
    2013
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Continuing Grant

相似海外基金

Collaborative Research: AF: Medium: The Communication Cost of Distributed Computation
合作研究:AF:媒介:分布式计算的通信成本
  • 批准号:
    2402836
  • 财政年份:
    2024
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: Foundations of Oblivious Reconfigurable Networks
合作研究:AF:媒介:遗忘可重构网络的基础
  • 批准号:
    2402851
  • 财政年份:
    2024
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: Algorithms Meet Machine Learning: Mitigating Uncertainty in Optimization
协作研究:AF:媒介:算法遇见机器学习:减轻优化中的不确定性
  • 批准号:
    2422926
  • 财政年份:
    2024
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: Fast Combinatorial Algorithms for (Dynamic) Matchings and Shortest Paths
合作研究:AF:中:(动态)匹配和最短路径的快速组合算法
  • 批准号:
    2402283
  • 财政年份:
    2024
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: Foundations of Oblivious Reconfigurable Networks
合作研究:AF:媒介:遗忘可重构网络的基础
  • 批准号:
    2402852
  • 财政年份:
    2024
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: Fast Combinatorial Algorithms for (Dynamic) Matchings and Shortest Paths
合作研究:AF:中:(动态)匹配和最短路径的快速组合算法
  • 批准号:
    2402284
  • 财政年份:
    2024
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: The Communication Cost of Distributed Computation
合作研究:AF:媒介:分布式计算的通信成本
  • 批准号:
    2402837
  • 财政年份:
    2024
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: The Communication Cost of Distributed Computation
合作研究:AF:媒介:分布式计算的通信成本
  • 批准号:
    2402835
  • 财政年份:
    2024
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: Adventures in Flatland: Algorithms for Modern Memories
合作研究:AF:媒介:平地历险记:现代记忆算法
  • 批准号:
    2423105
  • 财政年份:
    2024
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: Sketching for privacy and privacy for sketching
合作研究:AF:中:为隐私而素描和为素描而隐私
  • 批准号:
    2311649
  • 财政年份:
    2023
  • 资助金额:
    $ 17.5万
  • 项目类别:
    Continuing Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了