A Polynomial-Time Approximation Scheme for the Geometric Unique Coverage Problem on Unit Squares

DOI10.1007/978-3-642-31155-0_3MaRDI QIDQ2904540zbMATH OpenOpenAlexFDO

Authors Takehiro Ito, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Yushi Uno, Shin-Ichi Nakano

Publication date 14 August 2012

Published in Algorithm Theory – SWAT 2012 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-31155-0_3

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Recommendations

• A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares
• A 4.31-approximation for the geometric unique coverage problem on unit disks
• A 4.31-approximation for the geometric unique coverage problem on unit disks
• scientific article; zbMATH DE number 7378687
• The Parameterized Complexity of the Unique Coverage Problem
• Near-linear time approximation schemes for geometric maximum coverage
• Linear Time Approximation Schemes for Geometric Maximum Coverage
• An exact algorithm for a class of geometric set-cover problems
• Approximation algorithms for a geometric set cover problem
• The parameterized complexity of unique coverage and its variants

Cited in

(9)

• A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares
• A 4.31-approximation for the geometric unique coverage problem on unit disks
• Discrete unit square cover problem
• A 4.31-approximation for the geometric unique coverage problem on unit disks
• Local search strikes again: PTAS for variants of geometric covering and packing
• Unique coverage with rectangular regions
• Unique covering problems with geometric sets
• On nonlinear multi-covering problems
• Geometric red-blue set cover for unit squares and related problems

This page was built for publication: A Polynomial-Time Approximation Scheme for the Geometric Unique Coverage Problem on Unit Squares

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