On the Approximability of Orthogonal Order Preserving Layout Adjustment

DOI10.1007/978-3-319-21840-3_5zbMath1444.68271arXiv1502.03847OpenAlexW1648568888MaRDI QIDQ3449805

Sayan Bandyapadhyay, Santanu Bhowmick, Kasturi R. Varadarajan

Publication date: 30 October 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1502.03847

zbMATH Keywords

APX-hardnessconstant-factor approximation for LADRdecision version of LADR

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cites Work

• A \((5/3+\varepsilon)\)-approximation for strip packing
• Approximation algorithms for hitting objects with straight lines
• Label placement by maximum independent set in rectangles
• Point labeling with sliding labels
• Two-dimensional packing problems: a survey
• Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
• A threshold of ln n for approximating set cover
• Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• A User Study in Similarity Measures for Graph Drawing
• Orthogonal-Ordering Constraints are Tough
• A quasi-PTAS for the Two-Dimensional Geometric Knapsack Problem

This page was built for publication: On the Approximability of Orthogonal Order Preserving Layout Adjustment