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.1007/978-3-642-13731-0_28]

* [http://dx.doi.org/10.1016/j.comgeo.2011.10.004 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://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 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://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 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/xml],
: [https://api.elsevier.com/content/article/PII:S0925772111000800?httpAccept=text/plain https://api.elsevier.com/content/article/PII:S0925772111000800?httpAccept=text/plain],
: [http://dx.doi.org/10.1016/j.comgeo.2011.10.004 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://dblp.uni-trier.de/db/conf/swat/swat2010.html#BergG10],
: [https://www.win.tue.nl/~mdberg/Papers/2010/bg-aaflm-eurocg-10.pdf 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://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 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 http://ui.adsabs.harvard.edu/abs/2010LNCS.6139..297D/abstract],
: [https://doi.org/10.1007/978-3-642-13731-0_28 https://doi.org/10.1007/978-3-642-13731-0_28],
: [http://alexandria.tue.nl/openaccess/Metis239508.pdf http://alexandria.tue.nl/openaccess/Metis239508.pdf],
: [https://rd.springer.com/chapter/10.1007/978-3-642-13731-0_28 https://rd.springer.com/chapter/10.1007/978-3-642-13731-0_28],
: [https://academic.microsoft.com/#/detail/2110919917 https://academic.microsoft.com/#/detail/2110919917]

* [https://www.sciencedirect.com/science/article/pii/S0925772111000800 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://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://dblp.uni-trier.de/db/journals/comgeo/comgeo45.html#BergG12],
: [https://dl.acm.org/citation.cfm?id=2109239.2109581 https://dl.acm.org/citation.cfm?id=2109239.2109581],
: [https://doi.org/10.1016/j.comgeo.2011.10.004 https://doi.org/10.1016/j.comgeo.2011.10.004],
: [https://research.tue.nl/en/publications/approximation-algorithms-for-free-label-maximization-3 https://research.tue.nl/en/publications/approximation-algorithms-for-free-label-maximization-3],
: [https://academic.microsoft.com/#/detail/2030174981 https://academic.microsoft.com/#/detail/2030174981]





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