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

  • Berman, Piotr (PI)

    Project: Research project

    Project Details

    Description

    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.

    StatusFinished
    Effective start/end date9/1/022/28/06

    Funding

    • National Science Foundation: $81,245.00

    Fingerprint

    Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.