Improved approximation algorithms for rectangle tiling and packing

Piotr Berman; Bhaskar Dasgupta; S. Muthukrishnan; Suneeta Ramaswami

Improved approximation algorithms for rectangle tiling and packing

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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

Original language	English (US)
Title of host publication	Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms
Pages	427-436
Number of pages	10
State	Published - 2001
Event	2001 Operating Section Proceedings, American Gas Association - Dallas, TX, United States Duration: Apr 30 2001 → May 1 2001

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other	2001 Operating Section Proceedings, American Gas Association
Country/Territory	United States
City	Dallas, TX
Period	4/30/01 → 5/1/01

Keywords

Algorithms
Design
Measurement
Performance
Theory
Verification

ASJC Scopus subject areas

Software
General Mathematics

Cite this

Improved approximation algorithms for rectangle tiling and packing. / Berman, Piotr; Dasgupta, Bhaskar; Muthukrishnan, S. et al.
Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 2001. p. 427-436 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Berman, P, Dasgupta, B, Muthukrishnan, S & Ramaswami, S 2001, Improved approximation algorithms for rectangle tiling and packing. in Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 427-436, 2001 Operating Section Proceedings, American Gas Association, Dallas, TX, United States, 4/30/01.

@inproceedings{e47409111bf24d0cae2382e14158243c,

title = "Improved approximation algorithms for rectangle tiling and packing",

abstract = "We provide improved approximation algorithms for several rectangle tiling and packing problems (RTILE, DRTILE and d-RPACK) studied in the literature. Our algorithms are highly efficient since their running times are near-linear in the space input size rather than in the domain size. In addition, we improve the best known approximation ratios, in some cases quite significantly.",

keywords = "Algorithms, Design, Measurement, Performance, Theory, Verification",

author = "Piotr Berman and Bhaskar Dasgupta and S. Muthukrishnan and Suneeta Ramaswami",

year = "2001",

language = "English (US)",

isbn = "0898714907",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

pages = "427--436",

booktitle = "Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms",

note = "2001 Operating Section Proceedings, American Gas Association ; Conference date: 30-04-2001 Through 01-05-2001",

}

TY - GEN

T1 - Improved approximation algorithms for rectangle tiling and packing

AU - Berman, Piotr

AU - Dasgupta, Bhaskar

AU - Muthukrishnan, S.

AU - Ramaswami, Suneeta

PY - 2001

Y1 - 2001

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

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

KW - Algorithms

KW - Design

KW - Measurement

KW - Performance

KW - Theory

KW - Verification

UR - http://www.scopus.com/inward/record.url?scp=0003661392&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0003661392&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0003661392

SN - 0898714907

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 427

EP - 436

BT - Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 2001 Operating Section Proceedings, American Gas Association

Y2 - 30 April 2001 through 1 May 2001

ER -

Improved approximation algorithms for rectangle tiling and packing

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this