Efficient Approximation Algorithms for Tiling and Packing Problems with Rectangles

Piotr Berman, Bhaskar DasGupta, S. Muthukrishnan, Suneeta Ramaswami

    Research output: Contribution to journalArticlepeer-review

    Abstract

    We provide improved approximation algorithms for several rectangle tiling and packing problems (RTILE, DRTILE, and d-RPACK) studied in the literature. Most of our algorithms are highly efficient since their running times are near-linear in the sparse input size rather than in the domain size. In addition, we improve the best known approximation ratios.

    Original languageEnglish (US)
    Pages (from-to)443-470
    Number of pages28
    JournalJournal of Algorithms
    Volume41
    Issue number2
    DOIs
    StatePublished - Nov 2001

    ASJC Scopus subject areas

    • Control and Optimization
    • Computational Mathematics
    • Computational Theory and Mathematics

    Fingerprint Dive into the research topics of 'Efficient Approximation Algorithms for Tiling and Packing Problems with Rectangles'. Together they form a unique fingerprint.

    Cite this