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.

该协作项目的作用是设计，分析和实施有效的算法，用于在两个或更高维度中使用矩形的几个平铺，包装和涵盖问题，以及在不同领域的应用，例如：VLSI，计算机图形，图像处理，图像处理，数据库设计，数据挖掘和计算生物学。 由于为几乎所有这些问题计算精确的解决方案非常困难，因此目标是使用算法设计的各种统一技术，例如局部比例，多相方法，切片方法，切片方法，以及通过非平凡的圆形圆形和原始偶性架构进行线性编程。 他们将在网格上开发新的数据结构，以解决这些问题的有效近似算法。