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

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

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.