Approximation algorithms for free-label maximization

M.T. Berg, de, D.H.P. Gerrits

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

10 Citaten (Scopus)
1 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
Pagina's (van-tot)153-168
TijdschriftComputational Geometry
Volume45
Nummer van het tijdschrift4
DOI's
StatusGepubliceerd - 2012

Vingerafdruk Duik in de onderzoeksthema's van 'Approximation algorithms for free-label maximization'. Samen vormen ze een unieke vingerafdruk.

Citeer dit