Book chapter
On the Approximability of Orthogonal Order Preserving Layout Adjustment
Algorithms and Data Structures, pp.54-65
Lecture Notes in Computer Science, Springer International Publishing
07/28/2015
DOI: 10.1007/978-3-319-21840-3_5
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 NP\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$\mathbb {NP}$$\end{document}-hard, but only heuristics were known for it. We show that a certain decision version of LADR is APX\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$\mathbb {APX}$$\end{document}-hard, and give a constant factor approximation for LADR.
Details
- Title: Subtitle
- On the Approximability of Orthogonal Order Preserving Layout Adjustment
- Creators
- Sayan Bandyapadhyay - University of IowaSantanu Bhowmick - University of IowaKasturi Varadarajan - University of Iowa
- Resource Type
- Book chapter
- Publication Details
- Algorithms and Data Structures, pp.54-65
- Publisher
- Springer International Publishing; Cham
- Series
- Lecture Notes in Computer Science
- DOI
- 10.1007/978-3-319-21840-3_5
- eISSN
- 1611-3349
- ISSN
- 0302-9743
- Language
- English
- Date published
- 07/28/2015
- Academic Unit
- Computer Science
- Record Identifier
- 9984259660202771
Metrics
4 Record Views