Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс: http://elar.urfu.ru/handle/10995/102462
Название: Semantic word cloud representations: Hardness and approximation algorithms
Авторы: Barth, L.
Fabrikant, S. I.
Kobourov, S. G.
Lubiw, A.
Nöllenburg, M.
Okamoto, Y.
Pupyrev, S.
Squarcella, C.
Ueckerdt, T.
Wolff, A.
Дата публикации: 2014
Издатель: Springer Verlag
Библиографическое описание: Semantic word cloud representations: Hardness and approximation algorithms / L. Barth, S. I. Fabrikant, S. G. Kobourov, et al. — DOI 10.1007/978-3-642-54423-1_45 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2014. — Vol. 8392 LNCS. — P. 514-525.
Аннотация: We study a geometric representation problem, where we are given a set of axis-aligned rectangles (boxes) with fixed dimensions and a graph with vertex set. The task is to place the rectangles without overlap such that two rectangles touch if the graph contains an edge between them. We call this problem Contact Representation of Word Networks (Crown). It formalizes the geometric problem behind drawing word clouds in which semantically related words are close to each other. Here, we represent words by rectangles and semantic relationships by edges. We show that Crown is strongly NP-hard even if restricted to trees and weakly NP-hard if restricted to stars. We also consider the optimization problem Max-Crown where each adjacency induces a certain profit and the task is to maximize the sum of the profits. For this problem, we present constant-factor approximations for several graph classes, namely stars, trees, planar graphs, and graphs of bounded degree. Finally, we evaluate the algorithms experimentally and show that our best method improves upon the best existing heuristic by 45%. © 2014 Springer-Verlag Berlin Heidelberg.
Ключевые слова: APPROXIMATION ALGORITHMS
DATA MINING
FORESTRY
GEOMETRY
HEURISTIC ALGORITHMS
HEURISTIC METHODS
INFORMATION SCIENCE
PROFITABILITY
SEMANTICS
STARS
BOUNDED DEGREE
CONSTANT FACTOR APPROXIMATION
GEOMETRIC PROBLEMS
GEOMETRIC REPRESENTATION
OPTIMIZATION PROBLEMS
SEMANTIC RELATIONSHIPS
SEMANTICALLY-RELATED WORDS
STRONGLY NP-HARD
TREES (MATHEMATICS)
ALGORITHMS
DATA PROCESSING
FORESTRY
INFORMATION RETRIEVAL
PROFITABILITY
URI: http://elar.urfu.ru/handle/10995/102462
Условия доступа: info:eu-repo/semantics/openAccess
Идентификатор SCOPUS: 84899939512
Идентификатор PURE: 1596653
fb2552c7-1825-4986-96cd-479080fbfaec
ISSN: 3029743
ISBN: 9783642544224
DOI: 10.1007/978-3-642-54423-1_45
Располагается в коллекциях:Научные публикации, проиндексированные в SCOPUS и WoS CC

Файлы этого ресурса:
Файл Описание РазмерФормат 
2-s2.0-84899939512.pdf1,09 MBAdobe PDFПросмотреть/Открыть


Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.