Collaborative Research: Efficient Combinatorial Algorithms for Several Tiling, Packing and Covering Problems with Rectangles and Hyper-Rectangles

协作研究：针对矩形和超矩形的多个平铺、填充和覆盖问题的高效组合算法

• 批准号: 0208749
• 负责人: Bhaskar DasGupta
• 金额: $ 14.41万
• 依托单位: University of Illinois at Chicago
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-09-01 至 2005-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0208749&HistoricalAwards=false
• 关键词: Collaborative; Research; Efficient; Combinatorial; Algorithms

The thrust of this collaborative project is to design, analyze and implement efficient algorithms for several tiling, packing and covering problems with rectangles in two or higher dimensions with applications in diverse areas such as: VLSI, computer graphics, image processing, database design, data mining and computational biology. Since computing exact solutions for almost all of these problems is provably hard, the goal is to use diverse unifying techniques of algorithm design such as local-ratio, multi-phase methods, and slice-and-dice methods, and linear programming with nontrivial rounding and primal-dual schema. They will develop novel data structures on grids for efficient approximation algorithms for these problems.

这个合作项目的主旨是设计，分析和实施有效的算法，在两个或更高的维度与应用程序在不同的领域，如：超大规模集成电路，计算机图形学，图像处理，数据库设计，数据挖掘和计算生物学的矩形平铺，包装和覆盖问题。 由于计算几乎所有这些问题的精确解是证明困难的，目标是使用不同的统一技术的算法设计，如本地比率，多阶段的方法，切片和骰子的方法，和线性规划与非平凡舍入和原始对偶模式。 他们将在网格上开发新的数据结构，用于这些问题的有效近似算法。