University of Sussex
Browse

File(s) not publicly available

Inapproximability results for orthogonal rectangle packing problems with rotations

presentation
posted on 2023-06-08, 06:38 authored by Miroslav ChlebikMiroslav Chlebik, Janka Chlebíková
Recently Bansal and Sviridenko [4] proved that there is no asymptotic PTAS for 2-DIMENSIONAL ORTHOGONAL RECTANGLE BIN PACKING without rotations allowed, unless P = NP. We show that similar approximation hardness results hold for several rectangle packing problems even if rotations by ninety degrees around the axes are allowed. Moreover, for some of these problems we provide explicit lower bounds on asymptotic approximation ratio of any polynomial time approximation algorithm.

History

Publication status

  • Published

ISSN

0302-9743

Publisher

SPRINGER-VERLAG BERLIN, HEIDELBERGER

Volume

LNCS 3

Pages

12.0

Presentation Type

  • paper

Event name

6th Italian Conference on Algorithms and Complexity (CIAC 2006)

Event location

Rome, ITALY

Event type

conference

ISBN

3-540-34375-X

Department affiliated with

  • Mathematics Publications

Notes

ALGORITHMS AND COMPLEXITY, PROCEEDINGS

Full text available

  • No

Peer reviewed?

  • Yes

Editors

GF Italiano, T Calamoneri, I Finocchi

Legacy Posted Date

2012-02-06

Usage metrics

    University of Sussex (Publications)

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC