Beyond Maximum Independent Set: An Extended Integer
Programming Formulation for Point Labeling
International Journal of Geo-Information, 6 (11):
article 342, 20 pages (2017)DOI: 10.3390/ijgi6110342
Abstract
Map labeling is a classical problem of cartography
that has frequently been approached by combinatorial
optimization. Given a set of features in a map and
for each feature a set of label candidates, a common
problem is to select an independent set of labels
(that is, a labeling without label--label
intersections) that contains as many labels as
possible and at most one label for each feature. To
obtain solutions of high cartographic quality, the
labels can be weighted and one can maximize the
total weight (rather than the number) of the
selected labels. We argue, however, that when
maximizing the weight of the labeling, the
influences of labels on other labels are
insufficiently addressed. Furthermore, in a
maximum-weight labeling, the labels tend to be
densely packed and thus the map background can be
occluded too much. We propose extensions of an
existing model to overcome these limitations. Since
even without our extensions the problem is NP-hard,
we cannot hope for an efficient exact algorithm for
the problem. Therefore, we present a formalization
of our model as an integer linear program (ILP).
This allows us to compute optimal solutions in
reasonable time, which we demonstrate both for
randomly generated point sets and an existing data
set of cities. Moreover, a relaxation of our ILP
allows for a simple and efficient heuristic, which
yielded near-optimal solutions for our instances.
