Refine
Year of publication
- 2021 (2) (remove)
Document Type
- Article (1)
- Doctoral Thesis (1)
Is part of the Bibliography
- yes (2)
Keywords
- Algorithms (2) (remove)
Institute
In the last decades, there was a notable progress in solving the well-known Boolean satisfiability (Sat) problem, which can be witnessed by powerful Sat solvers. One of the reasons why these solvers are so fast are structural properties of instances that are utilized by the solver’s interna. This thesis deals with the well-studied structural property treewidth, which measures the closeness of an instance to being a tree. In fact, there are many problems parameterized by treewidth that are solvable in polynomial time in the instance size when parameterized by treewidth.
In this work, we study advanced treewidth-based methods and tools for problems in knowledge representation and reasoning (KR). Thereby, we provide means to establish precise runtime results (upper bounds) for canonical problems relevant to KR. Then, we present a new type of problem reduction, which we call decomposition-guided (DG) that
allows us to precisely monitor the treewidth when reducing from one problem to another problem. This new reduction type will be the basis for a long-open lower bound result for quantified Boolean formulas and allows us to design a new methodology for establishing runtime lower bounds for problems parameterized by treewidth.
Finally, despite these lower bounds, we provide an efficient implementation of algorithms that adhere to treewidth. Our approach finds suitable abstractions of instances, which are subsequently refined in a recursive fashion, and it uses Sat solvers for solving subproblems. It turns out that our resulting solver is quite competitive for two canonical counting problems related to Sat.
Organisation und Algorithmus
(2021)
Der vorliegende Beitrag analysiert, wie Organisationen Algorithmen, die wir als digitale Beobachtungsformate verstehen, mit Handlungsfähigkeit ausstatten und damit actionable machen. Das zentrale Argument lautet, dass die soziale Relevanz digitaler Beobachtungsformate sich daraus ergibt, dass und wie sie in organisationale Entscheidungsarchitekturen eingebettet sind. Diesen Zusammenhang illustrieren wir am Beispiel des österreichischen Arbeitsmarktservice (AMS), der 2018 einen Algorithmus einführte, um die Integrationschancen arbeitsuchender Personen zu bewerten. Der AMS steht dabei stellvertretend für aktuelle Bestrebungen vieler Organisationen, algorithmische Systeme einzusetzen, um knappe öffentliche Ressourcen vermeintlich effizienter zu distribuieren. Um zu rekonstruieren, wie dies geschieht, zeigen wir, welche Operationen des Kategorisierens, Vergleichens und Bewertens das algorithmische Modell vollzieht. Darauf aufbauend demonstrieren wir, wie das algorithmische Modell in die organisationale Entscheidungsarchitektur eingebunden ist. Erst durch diese Einbindung – die Möglichkeit, Unterschiede für andere, relativ stabil erzeugte Entscheidungen zu machen – entfaltet das digitale Beobachtungsformat soziale Relevanz. Abschließend argumentieren wir, dass algorithmische Modelle, wie sie am Fall des AMS beobachtet werden können, dazu tendieren, sich in Organisationen zu stabilisieren. Dies begründen wir damit, dass die organisationalen Lernchancen im Umgang mit dem Algorithmus dadurch reduziert sind, dass dieser in einem Bereich zum Einsatz kommt, der durch Technologiedefizit und koproduktive Leistungserstellung geprägt ist.