A Constant Factor Approximation for Orthogonal Order Preserving Layout Adjustment

Sayan Bandyapadhyay; Santanu Bhowmick; Kasturi Varadarajan

doi:10.48550/arxiv.1502.03847

Back

A Constant Factor Approximation for Orthogonal Order Preserving Layout Adjustment

Preprint

Open access

A Constant Factor Approximation for Orthogonal Order Preserving Layout Adjustment

Sayan Bandyapadhyay, Santanu Bhowmick and Kasturi Varadarajan

ArXiv.org

02/12/2015

DOI: 10.48550/arxiv.1502.03847

Files and links (1)

url

https://doi.org/10.48550/arXiv.1602.04152View

Preprint (Author's original)This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. Open Access

Abstract

Given an initial placement of a set of rectangles in the plane, we consider the problem of finding a disjoint placement of the rectangles that minimizes the area of the bounding box and preserves the orthogonal order i.e.\ maintains the sorted ordering of the rectangle centers along both $x$-axis and $y$-axis with respect to the initial placement. This problem is known as Layout Adjustment for Disjoint Rectangles(LADR). It was known that LADR is $\mathbb{NP}$-hard, but only heuristics were known for it. We show that a certain decision version of LADR is $\mathbb{APX}$-hard, and give a constant factor approximation for LADR.

Details

Title: Subtitle: A Constant Factor Approximation for Orthogonal Order Preserving Layout Adjustment
Creators: Sayan Bandyapadhyay
Santanu Bhowmick
Kasturi Varadarajan
Resource Type: Preprint
Publication Details: ArXiv.org
DOI: 10.48550/arxiv.1502.03847
ISSN: 2331-8422
Language: English
Date posted: 02/12/2015
Academic Unit: Computer Science
Record Identifier: 9984411253602771

Metrics

3 Record Views