A PTAS for the square tiling problem

DOI10.1016/J.TCS.2014.09.012MaRDI QIDQ476839zbMATH OpenOpenAlexFDO

Authors Amihood Amir, Alberto Apostolico, Gad M. Landau, Ely Porat, Oren Sar Shalom

Publication date 2 December 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2014.09.012

zbMATH Keywords

NP-hardnessfinite alphabetstwo-dimensional tiling

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Combinatorial aspects of tessellation and tiling problems (05B45)

Recommendations

• Hard tiling problems with simple tiles
• Approximation algorithms for MAX–MIN tiling
• Rectangular Tiling in Multidimensional Arrays
• Tiling simply connected regions with rectangles
• scientific article; zbMATH DE number 1305473

Cites work

• scientific article; zbMATH DE number 3829300 (Why is no real title available?)
• scientific article; zbMATH DE number 1746652 (Why is no real title available?)
• scientific article; zbMATH DE number 770083 (Why is no real title available?)
• A Note on Approximation Schemes for Multidimensional Knapsack Problems
• Algorithms on Strings, Trees and Sequences
• Efficient text fingerprinting via Parikh mapping
• Indexing and retrieval of audio: A survey
• Introduction to Information Retrieval
• On Context-Free Languages

Cited in

(3)

• Towards a theory of patches
• Tile complexity of approximate squares
• scientific article; zbMATH DE number 1460255 (Why is no real title available?)

This page was built for publication: A PTAS for the square tiling problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q476839)