Approximation algorithms for free-label maximization

Abstract

Inspired by air-traffic control and other applications where moving objects have to be labeled, we consider the following (static) point-labeling problem: given a set P of n points in the plane and labels that are unit squares, place a label with each point in P in such a way that the number of free labels (labels not intersecting any other label) is maximized. We develop efficient constant-factor approximation algorithms for this problem, as well as PTASs, for various label-placement models.

Original document

The different versions of the original document can be found in:

• http://dx.doi.org/10.1007/978-3-642-13731-0_28

• http://dx.doi.org/10.1016/j.comgeo.2011.10.004 under the license http://www.elsevier.com/open-access/userlicense/1.0/

• https://doi.org/10.1016/j.comgeo.2011.10.004

• https://research.tue.nl/nl/publications/approximation-algorithms-for-freelabel-maximization(77caa8cb-6272-4880-b521-52acf79ba904).html

• http://link.springer.com/content/pdf/10.1007/978-3-642-13731-0_28,

http://dx.doi.org/10.1007/978-3-642-13731-0_28

• https://api.elsevier.com/content/article/PII:S0925772111000800?httpAccept=text/xml,

https://api.elsevier.com/content/article/PII:S0925772111000800?httpAccept=text/plain,

http://dx.doi.org/10.1016/j.comgeo.2011.10.004 under the license https://www.elsevier.com/tdm/userlicense/1.0/

• https://dblp.uni-trier.de/db/conf/swat/swat2010.html#BergG10,

https://www.win.tue.nl/~mdberg/Papers/2010/bg-aaflm-eurocg-10.pdf,

https://link.springer.com/chapter/10.1007/978-3-642-13731-0_28,

https://www.narcis.nl/publication/RecordID/oai%3Apure.tue.nl%3Apublications%2Fdf4f0ffc-36e8-45ea-a768-a1dd37dd3010,

http://ui.adsabs.harvard.edu/abs/2010LNCS.6139..297D/abstract,

https://doi.org/10.1007/978-3-642-13731-0_28,

http://alexandria.tue.nl/openaccess/Metis239508.pdf,

https://rd.springer.com/chapter/10.1007/978-3-642-13731-0_28,

https://academic.microsoft.com/#/detail/2110919917

• https://www.sciencedirect.com/science/article/pii/S0925772111000800,

https://www.narcis.nl/publication/RecordID/oai%3Apure.tue.nl%3Apublications%2F77caa8cb-6272-4880-b521-52acf79ba904,

https://dblp.uni-trier.de/db/journals/comgeo/comgeo45.html#BergG12,

https://dl.acm.org/citation.cfm?id=2109239.2109581,

https://doi.org/10.1016/j.comgeo.2011.10.004,

https://research.tue.nl/en/publications/approximation-algorithms-for-free-label-maximization-3,

https://academic.microsoft.com/#/detail/2030174981

DOIS: 10.1016/j.comgeo.2011.10.004 10.1007/978-3-642-13731-0_28