Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

A Minimum Set-Cover Problem with several constraints

: Dörpinghaus, Jens; Düing, Carsten; Weil, Vera


Ganzha, M. ; Institute of Electrical and Electronics Engineers -IEEE-:
Federated Conference on Computer Science and Information Systems, FedCSIS 2019. Proceedings : September 1-4, 2019, Leipzig, Germany
Piscataway, NJ: IEEE, 2019 (Annals of Computer Science and Information Systems 18)
ISBN: 978-1-5386-8005-6
ISBN: 978-83-952357-8-8
Federated Conference on Computer Science and Information Systems (FedCSIS) <2019, Leipzig>
Fraunhofer SCAI ()

A lot of problems in natural language processing can be interpreted using structures from discrete mathematics. In this paper we will discuss the search query and topic finding problem using a generic context-based approach. This problem can be described as a Minimum Set Cover Problem with several constraints. The goal is to find a minimum covering of documents with the given context for a fixed weight function. The aim of this problem reformulation is a deeper understanding of both the hierarchical problem using union and cut as well as the non-hierarchical problem using the union. We thus choose a modeling using bipartite graphs and suggest a novel reformulation using an integer linear program as well as novel graph-theoretic approaches.