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、计算机图形学、图像处理、数据库设计、数据采矿和计算生物学。 由于计算几乎所有这些问题的精确解决方案都非常困难，因此目标是使用算法设计的多种统一技术，例如局部比率、多阶段方法、切片和切块方法，以及具有非平凡舍入的线性规划和原始对偶模式。 他们将在网格上开发新颖的数据结构，以实现这些问题的有效近似算法。