Source author record

Lutz Oettershagen

Lutz Oettershagen appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Information Retrieval Computational Complexity Databases Social and Information Networks

Catalog footprint

What is connected

4works

5topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2026arXiv

Streaming Stochastic Submodular Maximization with On-Demand User Requests

We explore a novel problem in streaming submodular maximization, inspired by the dynamics of news-recommendation platforms. We consider a setting where users can visit a news website at any time, and upon each visit, the website must display up to $k$ news items. User interactions are inherently stochastic: each news item presented to the user is consumed with a certain acceptance probability by the user, and each news item covers certain topics. Our goal is to design a streaming algorithm that maximizes the expected total topic coverage. To address this problem, we establish a connection to submodular maximization subject to a matroid constraint. We show that we can effectively adapt previous methods to address our problem when the number of user visits is known in advance or linear-size memory in the stream length is available. However, in more realistic scenarios where only an upper bound on the visits and sublinear memory is available, the algorithms fail to guarantee any bounded performance. To overcome these limitations, we introduce a new online streaming algorithm that achieves a competitive ratio of $1/(8δ)$, where $δ$ controls the approximation quality. Moreover, it requires only a single pass over the stream, and uses memory independent of the stream length. Empirically, our algorithms consistently outperform the baselines.

preprint2023arXiv

An Index for Single Source All Destinations Distance Queries in Temporal Graphs

Temporal closeness is a generalization of the classical closeness centrality measure for analyzing evolving networks. The temporal closeness of a vertex $v$ is defined as the sum of the reciprocals of the temporal distances to the other vertices. Ranking all vertices of a network according to the temporal closeness is computationally expensive as it leads to a single-source-all-destination (SSAD) temporal distance query starting from each vertex of the graph. To reduce the running time of temporal closeness computations, we introduce an index to speed up SSAD temporal distance queries called Substream index. We show that deciding if a Substream index of a given size exists is NP-complete and provide an efficient greedy approximation. Moreover, we improve the running time of the approximation using min-hashing and parallelization. Our evaluation with real-world temporal networks shows a running time improvement of up to one order of magnitude compared to the state-of-the-art temporal closeness ranking algorithms.

preprint2022arXiv

Temporal Walk Centrality: Ranking Nodes in Evolving Networks

We propose the Temporal Walk Centrality, which quantifies the importance of a node by measuring its ability to obtain and distribute information in a temporal network. In contrast to the widely-used betweenness centrality, we assume that information does not necessarily spread on shortest paths but on temporal random walks that satisfy the time constraints of the network. We show that temporal walk centrality can identify nodes playing central roles in dissemination processes that might not be detected by related betweenness concepts and other common static and temporal centrality measures. We propose exact and approximation algorithms with different running times depending on the properties of the temporal network and parameters of our new centrality measure. A technical contribution is a general approach to lift existing algebraic methods for counting walks in static networks to temporal networks. Our experiments on real-world temporal networks show the efficiency and accuracy of our algorithms. Finally, we demonstrate that the rankings by temporal walk centrality often differ significantly from those of other state-of-the-art temporal centralities.

preprint2020arXiv

On the Enumeration and Counting of Bicriteria Temporal Paths

We discuss the complexity of path enumeration and counting in weighted temporal graphs. In a weighted temporal graph, each edge has an availability time, a traversal time and some real cost. We introduce two bicriteria temporal min-cost path problems in which we are interested in the set of all efficient paths with low cost and short duration or early arrival time, respectively. However, the number of efficient paths can be exponential in the size of the input. For the case of strictly positive edge costs we are able to provide algorithms that enumerate the set of efficient paths with polynomial time delay and polynomial space. If we are only interested in the set of Pareto-optimal solutions and not in the paths themselves, then these can be determined in polynomial time if all edge costs are nonnegative. In addition, for each Pareto-optimal solution, we are able to find an efficient path in polynomial time. On the negative side, we prove that counting the number of efficient paths is #P-complete, even in the non-weighted single criterion case.