Paper Info
Title
A lagrangean decomposition for the maximum independent set problem applied to map labeling.
Abstract
The Maximum Independent Set (MIS) problem is a well-known problem where the aim is to find the maximum cardinality independent set in an associated graph. Map labeling problems can often be modeled as a MIS problem in a conflict graph, where labels are selected to be placed near graphical features not allowing overlaps (conflicts) between labels or between labels and features. However, the MIS problem is NP-hard and exact techniques present difficulties for solving some instances. Thus, this paper presents a Lagrangean decomposition to solve a map labeling problem, the Point-Feature Label Placement problem. We treated the problem by a conflict graph that is partitioned into small sub-problems and copies of some decision variables are done. These copies are used in the sub-problems constraints and in some constraints to ensure the equality between the original variables and their copies. After these steps, we relax these copy constraints in a Lagrangean way. Using instances proposed in the literature, our approach was able to prove the optimality for all of them, except one, and the results were better than the ones provided by a commercial solver.
Year
DOI
Venue
2011
10.1007/s12351-009-0075-1
Operational Research
Keywords
DocType
Volume
Label placement, Maximum independent set, Lagrangean decomposition, Lagrangean relaxation, 90C27, 90C05
Journal
11
Issue
ISSN
Citations 
3
1866-1505
0
PageRank 
References 
Authors
0.34
11
3
Name
Order
Citations
PageRank
Glaydston Mattos Ribeiro120213.79
Geraldo R. Mauri2292.92
Luiz Antonio Nogueira Lorena349836.72