We study the $k$-center problem in the context of individual fairness. Let $P$ be a set of $n$ points in a metric space and $r_x$ be the distance between $x \in P$ and its $\lceil n/k \rceil$-th nearest neighbor. The problem asks to optimize the $k$-center objective under the constraint that, for every point $x$, there is a center within distance $r_x$. We give bicriteria $(\beta,\gamma)$-approximation algorithms that compute clusterings such that every point $x \in P$ has a center within distance $\beta r_x$ and the clustering cost is at most $\gamma$ times the optimal cost. Our main contributions are a deterministic $O(n^2+ kn \log n)$ time $(2,2)$-approximation algorithm and a randomized $O(nk\log(n/\delta)+k^2/\varepsilon)$ time $(10,2+\varepsilon)$-approximation algorithm, where $\delta$ denotes the failure probability. For the latter, we develop a randomized sampling procedure to compute constant factor approximations for the values $r_x$ for all $x\in P$ in subquadratic time; we believe this procedure to be of independent interest within the context of individual fairness.

This paper aims to analyze longitudinal data, serial data related to different time points, in knowledge graphs.Knowledge graphs play a central role for linking different data.While multiple layers for data from different sources are considered, there is only very limited research on longitudinal data in knowledge graphs.However, knowledge graphs are widely used in big data integration, especially for connecting data from different domains.Few studies have investigated the questions how multiple layers and time points within graphs impact methods and algorithms developed for single-purpose networks.This manuscript investigates the impact of a modeling of longitudinal data in multiple layers on retrieval algorithms.In particular, (a) we propose a first draft of a generic model for longitudinal data in multi-layer knowledge graphs, (b) we develop an experimental environment to evaluate a generic retrieval algorithm on random graphs inspired by computational social sciences.We present a knowledge graph generated on German job advertisements comprising data from different sources, both structured and unstructured, on data between 2011 and 2021.The data is linked using text mining and natural language processing methods.We further (c) present two different shrinking techniques for structured and unstructured layers in knowledge based on graph structures like triangles and pseudo-triangles.The presented approach (d) shows that on the one hand, the initial research questions, on the other hand the graph structures and topology have a great impact on the structures and efficiency for additional data stored.Although the experimental analysis of random graphs allows us to make some basic observations we will (e) make suggestions for additional research on particular graph structures that have a great impact on the analysis of knowledge graph structures.

Knowledge graphs have been shown to play an important role in recent knowledge mining settings, for example in the fields of life sciences or bioinformatics.Contextual information is widely used for NLP and knowledge discovery tasks, since it highly influences the exact meaning of expressions and also queries on data.The contributions of this paper are (1) an efficient approach towards interoperable data, (2) a runtime analysis of 14 realworld use cases represented by graph queries and (3) a unique view on clinical data and its application, combining methods of algorithmic optimisation, graph theory and data science.

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 nonhierarchical 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.