Approximation algorithms for free-label maximization

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

doi:10.1007/978-3-642-13731-0_28

Approximation algorithms for free-label maximization

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

Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

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 language	English
Title of host publication	Algorithm Theory - SWAT 2010 (12th Scandinavian Symposium and Workshops on Algorithm Theory, Bergen, Norway, June 21-23, 2010. Proceedings)
Editors	H. Kaplan
Place of Publication	Berlin
Publisher	Springer
Pages	297-308
ISBN (Print)	978-3-642-13730-3
DOIs	https://doi.org/10.1007/978-3-642-13731-0_28
Publication status	Published - 2010

Publication series

Name	Lecture Notes in Computer Science
Volume	6139
ISSN (Print)	0302-9743

Access to Document

10.1007/978-3-642-13731-0_28

Fingerprint Dive into the research topics of 'Approximation algorithms for free-label maximization'. Together they form a unique fingerprint.

Cite this

Berg, de, M. T., & Gerrits, D. H. P. (2010). Approximation algorithms for free-label maximization. In H. Kaplan (Ed.), Algorithm Theory - SWAT 2010 (12th Scandinavian Symposium and Workshops on Algorithm Theory, Bergen, Norway, June 21-23, 2010. Proceedings) (pp. 297-308). (Lecture Notes in Computer Science; Vol. 6139). Springer. https://doi.org/10.1007/978-3-642-13731-0_28

@inproceedings{39e99e5ad9f44edabc548824f9096d62,

title = "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.",

author = "{Berg, de}, M.T. and D.H.P. Gerrits",

year = "2010",

doi = "10.1007/978-3-642-13731-0_28",

language = "English",

isbn = "978-3-642-13730-3",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "297--308",

editor = "H. Kaplan",

booktitle = "Algorithm Theory - SWAT 2010 (12th Scandinavian Symposium and Workshops on Algorithm Theory, Bergen, Norway, June 21-23, 2010. Proceedings)",

address = "Germany",

}

Approximation algorithms for free-label maximization. / Berg, de, M.T.; Gerrits, D.H.P.

Algorithm Theory - SWAT 2010 (12th Scandinavian Symposium and Workshops on Algorithm Theory, Bergen, Norway, June 21-23, 2010. Proceedings). ed. / H. Kaplan. Berlin : Springer, 2010. p. 297-308 (Lecture Notes in Computer Science; Vol. 6139).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Approximation algorithms for free-label maximization

AU - Berg, de, M.T.

AU - Gerrits, D.H.P.

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-13731-0_28

DO - 10.1007/978-3-642-13731-0_28

M3 - Conference contribution

SN - 978-3-642-13730-3

T3 - Lecture Notes in Computer Science

SP - 297

EP - 308

BT - Algorithm Theory - SWAT 2010 (12th Scandinavian Symposium and Workshops on Algorithm Theory, Bergen, Norway, June 21-23, 2010. Proceedings)

A2 - Kaplan, H.

PB - Springer

CY - Berlin

ER -