Incremental Approximations

增量近似

• 批准号: 9120731
• 负责人: Errol Lloyd
• 金额: $ 9.41万
• 依托单位: University of Delaware
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1992
• 资助国家: 美国
• 起止时间: 1992-09-15 至 1995-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9120731&HistoricalAwards=false
• 关键词: Incremental; Approximations

Although approximation algorithms and on-line algorithms have each been studied rather extensively, there has been very little work that examines the approximation and on-line aspects in tandem. That is, the design of approximation algorithms that work in an iterative fashion. The dual goals in designing such algorithms are to make the algorithm run fast, and to produce a good approximation. This research on incremental approximations is aimed at examining the tradeoffs and issues involved, as well as to develop incremental approximation methods for specific problems in register allocation, scheduling for packet radio networks, and bin-packing.

虽然近似算法和在线算法都得到了相当广泛的研究，但很少有工作同时考察近似和在线方面。也就是说，以迭代方式工作的近似算法的设计。设计这种算法的双重目标是使算法快速运行，并产生良好的近似。这项关于增量逼近的研究旨在检查所涉及的权衡和问题，以及为寄存器分配，分组无线网络调度和垃圾箱包装中的特定问题开发增量逼近方法。