| 1. Identity statement | |
| Reference Type | Journal Article |
| Site | mtc-m16d.sid.inpe.br |
| Holder Code | isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S |
| Identifier | 8JMKD3MGP7W/37JUAGE |
| Repository | sid.inpe.br/mtc-m19@80/2010/06.01.19.41 (restricted access) |
| Last Update | 2010:07.14.17.54.36 (UTC) administrator |
| Metadata Repository | sid.inpe.br/mtc-m19@80/2010/06.01.19.41.10 |
| Metadata Last Update | 2018:06.05.04.36.44 (UTC) administrator |
| Secondary Key | INPE--PRE/ |
| DOI | 10.1007/s12351-009-0075-1 |
| ISSN | 1866-1505 |
| Citation Key | RibeiroMaurLore:2010:LaDeMa |
| Title | A lagrangean decomposition for the maximum independent set problem applied to map labeling  |
| Year | 2010 |
| Access Date | 2024, Apr. 28 |
| Secondary Type | PRE PI |
| Number of Files | 1 |
| Size | 647 KiB |
| 2. Context | |
| Author | 1 Ribeiro, G. M. 2 Mauri, G. R. 3 Lorena, L. Antonio Nogueira |
| Group | 1 LAC-CTE-INPE-MCT-BR |
| Affiliation | 1 Universidade Federal do Espírito Santo 2 Universidade Federal do Espírito Santo 3 Instituto Nacional de Pesquisas Espaciais (INPE) |
| Journal | Operational Research |
| Volume | In press |
| History (UTC) | 2010-07-05 14:54:47 :: simone -> marciana :: 2010 2011-09-19 16:16:56 :: marciana -> administrator :: 2010 2018-06-05 04:36:44 :: administrator -> marciana :: 2010 |
| 3. Content and structure | |
| Is the master or a copy? | is the master |
| Content Stage | completed |
| Transferable | 1 |
| Content Type | External Contribution |
| Version Type | publisher |
| Keywords | Label placement Lagrangean decomposition Lagrangean relaxation Maximum independent set |
| 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. |
| Area | COMP |
| Arrangement | urlib.net > BDMCI > Fonds > Produção anterior à 2021 > LABAC > A lagrangean decomposition... |
| doc Directory Content | access |
| source Directory Content | there are no files |
| agreement Directory Content | there are no files |
| 4. Conditions of access and use | |
| Language | en |
| Target File | fulltextlorena.pdf |
| User Group | administrator marciana simone |
| Visibility | shown |
| Archiving Policy | denypublisher denyfinaldraft12 |
| Read Permission | deny from all and allow from 150.163 |
| Update Permission | not transferred |
| 5. Allied materials | |
| Mirror Repository | sid.inpe.br/mtc-m19@80/2009/08.21.17.02.53 |
| Next Higher Units | 8JMKD3MGPCW/3ESGTTP |
| Dissemination | WEBSCI; PORTALCAPES. |
| Host Collection | sid.inpe.br/mtc-m19@80/2009/08.21.17.02 |
| 6. Notes | |
| Empty Fields | alternatejournal archivist callnumber copyholder copyright creatorhistory descriptionlevel e-mailaddress electronicmailaddress format isbn label lineage mark month nextedition notes number orcid pages parameterlist parentrepositories previousedition previouslowerunit progress project readergroup resumeid rightsholder schedulinginformation secondarydate secondarymark session shorttitle sponsor subject tertiarymark tertiarytype typeofwork url |
| 7. Description control | |
| e-Mail (login) | marciana |
| update | |