%0 Journal Article
%@holdercode {isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S}
%@nexthigherunit 8JMKD3MGPCW/3ESGTTP
%@archivingpolicy denypublisher denyfinaldraft12
%X 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.
%@mirrorrepository sid.inpe.br/mtc-m19@80/2009/08.21.17.02.53
%T A lagrangean decomposition for the maximum independent set problem applied to map labeling
%@secondarytype PRE PI
%K Label placement, Lagrangean decomposition, Lagrangean relaxation, Maximum independent set.
%@usergroup administrator
%@usergroup marciana
%@usergroup simone
%@group LAC-CTE-INPE-MCT-BR
%3 fulltextlorena.pdf
%@secondarykey INPE--PRE/
%@issn 1866-1505
%2 sid.inpe.br/mtc-m19@80/2010/06.01.19.41.10
%@affiliation Universidade Federal do Espírito Santo
%@affiliation Universidade Federal do Espírito Santo
%@affiliation Instituto Nacional de Pesquisas Espaciais (INPE)
%B Operational Research
%@versiontype publisher
%4 sid.inpe.br/mtc-m19@80/2010/06.01.19.41
%@documentstage not transferred
%D 2010
%V In press
%@doi 10.1007/s12351-009-0075-1
%A Ribeiro, G. M.,
%A Mauri, G. R.,
%A Lorena, L. Antonio Nogueira,
%@dissemination WEBSCI; PORTALCAPES.
%@area COMP