Logo des Repositoriums

Auflistung nach Schlagwort "Completeness"

1 - 2 von 2
  • Textdokument
    Addressing the Log Representativeness Problem using Species Discovery (Extended Abstract)
    (EMISA 2024, 2024) Kabierski, Martin; Richter, Markus; Weidlich, Matthias
    Event logs are generated during the enactment of process-centric information systems and form the basis for optimization, monitoring, and enhancement initiatives of said systems. As such, they enable a data-driven and unbiased evaluation of the as-is state of the underlying processes. Yet, since at any time, event logs represent merely a sample of the whole possible behaviour of the information system, insights are only actionable should the event log be representative of the information system from which it is derived. Therefore, the question arises of how the representativeness of an event log$L with respect to its generative system P can be quantified, given that only L is present. In this work, we argue, that representativeness of an event log needs to be assessed with an intended analysis question in mind and discuss log completeness as one important facet of representativeness. We show how established estimators from biodiversity research can be utilized to quantify log completeness.
  • Zeitschriftenartikel
    The power of locality: Exploring the limits of randomness in distributed computing
    (it - Information Technology: Vol. 62, No. 5-6, 2020) Maus, Yannic
    Many modern systems are built on top of large-scale networks like the Internet. This article provides an overview of a dissertation [29] that addresses the complexity of classic graph problems like the vertex coloring problem in such networks. It has been known for a long time that randomization helps significantly in solving many of these problems, whereas the best known deterministic algorithms have been exponentially slower. In the first part of the dissertation we use a complexity theoretic approach to show that several problems are complete in the following sense: An efficient deterministic algorithm for any complete problem would imply an efficient algorithm for all problems that can be solved efficiently with a randomized algorithm. Among the complete problems is a rudimentary looking graph coloring problem that can be solved by a randomized algorithm without any communication. In further parts of the dissertation we develop efficient distributed algorithms for several problems where the most important problems are distributed versions of integer linear programs, the vertex coloring problem and the edge coloring problem. We also prove a lower bound on the runtime of any deterministic algorithm that solves the vertex coloring problem in a weak variant of the standard model of the area.