On the rectangle escape problem

DOI10.1016/j.tcs.2017.05.040zbMath1372.68245OpenAlexW2621825475MaRDI QIDQ2402267

Sadra Yazdanbod, Ehsan Emamjomeh-Zadeh, Sepehr Assadi, Hamid Zarrabi-Zadeh, AmirMahdi Ahmadinejad

Publication date: 7 September 2017

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

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

zbMATH Keywords

NP-completenessapproximation algorithmsrandomized roundinginapproximabilityrectangle escape

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (1)

An algorithm for the maximum weight independent set problem on outerstring graphs

Cites Work

• Randomized rounding: A technique for provably good algorithms and algorithmic proofs

This page was built for publication: On the rectangle escape problem