A PTAS for the square tiling problem

DOI10.1016/J.TCS.2014.09.012zbMath1303.68058OpenAlexW2026940253MaRDI QIDQ476839

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

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) Combinatorial aspects of tessellation and tiling problems (05B45) Approximation algorithms (68W25)

Cites Work

• Efficient text fingerprinting via Parikh mapping
• Introduction to Information Retrieval
• A Note on Approximation Schemes for Multidimensional Knapsack Problems
• Algorithms on Strings, Trees and Sequences
• On Context-Free Languages
• Indexing and retrieval of audio: A survey
• Unnamed Item
• Unnamed Item
• Unnamed Item

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