
Atenção:
O eduCAPES é um repositório de objetos educacionais, não sendo responsável por materiais de terceiros submetidos na plataforma. O usuário assume ampla e total responsabilidade quanto à originalidade, à titularidade e ao conteúdo, citações de obras consultadas, referências e outros elementos que fazem parte do material que deseja submeter. Recomendamos que se reporte diretamente ao(s) autor(es), indicando qual parte do material foi considerada imprópria (cite página e parágrafo) e justificando sua denúncia.
Caso seja o autor original de algum material publicado indevidamente ou sem autorização, será necessário que se identifique informando nome completo, CPF e data de nascimento. Caso possua uma decisão judicial para retirada do material, solicitamos que informe o link de acesso ao documento, bem como quaisquer dados necessários ao acesso, no campo abaixo.
Todas as denúncias são sigilosas e sua identidade será preservada. Os campos nome e e-mail são de preenchimento opcional. Porém, ao deixar de informar seu e-mail, um possível retorno será inviabilizado e/ou sua denúncia poderá ser desconsiderada no caso de necessitar de informações complementares.
| Metadados | Descrição | Idioma |
|---|---|---|
| Autor(es): dc.creator | Guimarães, Dilson Almeida | - |
| Autor(es): dc.creator | Cunha, Alexandre Salles da | - |
| Autor(es): dc.creator | Pereira, Dilson Lucas | - |
| Data de aceite: dc.date.accessioned | 2026-02-09T11:40:12Z | - |
| Data de disponibilização: dc.date.available | 2026-02-09T11:40:12Z | - |
| Data de envio: dc.date.issued | 2020-04-06 | - |
| Data de envio: dc.date.issued | 2020-04-06 | - |
| Data de envio: dc.date.issued | 2019-12 | - |
| Fonte completa do material: dc.identifier | https://repositorio.ufla.br/handle/1/39813 | - |
| Fonte completa do material: dc.identifier | https://www.sciencedirect.com/science/article/pii/S0377221719306022 | - |
| Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/1144805 | - |
| Descrição: dc.description | In this paper, we investigate Semidefinite Programming (SDP) lower bounds for the Quadratic Minimum Spanning Tree Problem (QMSTP). Two SDP lower bounding approaches are introduced here. Both apply Lagrangian Relaxation to an SDP relaxation for the problem. The first one explicitly dualizes the semidefiniteness constraint, attaching to it a positive semidefinite matrix of Lagrangian multipliers. The second relies on a semi-infinite reformulation for the cone of positive semidefinite matrices and dualizes a dynamically updated finite set of inequalities that approximate the cone. These lower bounding procedures are the core ingredient of two QMSTP Branch-and-bound algorithms. Our computational experiments indicate that the SDP bounds computed here are very strong, being able to close at least 70% of the gaps of the most competitive formulation in the literature. As a result, their accompanying Branch-and-bound algorithms are competitive with the best previously available QMSTP exact algorithm in the literature. In fact, one of these new Branch-and-bound algorithms stands out as the new best exact solution approach for the problem. | - |
| Idioma: dc.language | en | - |
| Publicador: dc.publisher | Elsevier | - |
| Direitos: dc.rights | restrictAccess | - |
| ???dc.source???: dc.source | European Journal of Operational Research | - |
| Palavras-chave: dc.subject | Combinatorial optimization | - |
| Palavras-chave: dc.subject | Spanning trees | - |
| Palavras-chave: dc.subject | Lagrangian relaxation | - |
| Palavras-chave: dc.subject | Semidefinite programming | - |
| Palavras-chave: dc.subject | Semi-infinite programming | - |
| Título: dc.title | Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem | - |
| Tipo de arquivo: dc.type | Artigo | - |
| Aparece nas coleções: | Repositório Institucional da Universidade Federal de Lavras (RIUFLA) | |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: