Semantic Word Cloud Representations: Hardness and Approximation Algorithms.
Lukas BarthSara Irina FabrikantStephen G. KobourovAnna LubiwMartin NöllenburgYoshio OkamotoSergey PupyrevClaudio SquarcellaTorsten UeckerdtAlexander WolffPublished in: LATIN (2014)
Keyphrases
- approximation algorithms
- np hard
- worst case
- np hardness
- special case
- semantic representations
- vertex cover
- minimum cost
- optimal solution
- constant factor
- exact algorithms
- cloud computing
- np complete
- linear programming
- word pairs
- lower bound
- network design problem
- set cover
- word similarity
- phase transition
- primal dual
- facility location problem
- approximation schemes
- natural language
- approximation ratio
- precedence constraints
- semantic similarity
- upper bound
- integer programming
- word sense disambiguation
- branch and bound
- open shop
- disjoint paths
- constant factor approximation