Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Arc-based integer programming formulations for three variants of proportional symbol maps

Texto completo
Autor(es):
Cano, Rafael G. [1] ; de Souza, Cid C. [1] ; de Rezende, Pedro J. [1] ; Yunes, Tallys [2]
Número total de Autores: 4
Afiliação do(s) autor(es):
[1] Univ Estadual Campinas, Inst Comp, BR-13083852 Campinas, SP - Brazil
[2] Univ Miami, Sch Business Adm, Coral Gables, FL 33124 - USA
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: DISCRETE OPTIMIZATION; v. 18, p. 87-110, NOV 2015.
Citações Web of Science: 1
Resumo

Proportional symbol maps are a cartographic tool that employs scaled symbols to represent data associated with specific locations. The symbols we consider are opaque disks, which may be partially covered by other overlapping disks. We address the problem of creating a suitable drawing of the disks that maximizes one of two quality metrics: the total and the minimum visible length of disk boundaries. We study three variants of this problem, two of which are known to be NP-hard and another whose complexity is open. We propose novel integer programming formulations for each problem variant and test them on real-world instances with a branch-and-cut algorithm. When compared with state-of-the-art models from the literature, our models significantly reduce computation times for most instances. (C) 2015 Elsevier B.V. All rights reserved. (AU)

Processo FAPESP: 07/52015-0 - Métodos de aproximação para computação visual
Beneficiário:Jorge Stolfi
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 12/00673-2 - Estudo de problemas de otimização combinatória relacionados a visualização de dados
Beneficiário:Rafael Ghussn Cano
Linha de fomento: Bolsas no Brasil - Doutorado Direto