東華大學圖書館 |

Multivariate Complexity Analyses for Algorithmic Challenges in Fairness and Sustainability = = Multivariate Komplexitatsanalysen von Algorithmischen Herausforderungen in Fairness und Nachhaltigkeit /

Record Type:	Electronic resources : Monograph/item
Title/Author:	Multivariate Complexity Analyses for Algorithmic Challenges in Fairness and Sustainability =/ Leon Kellerhals.
Reminder of title:	Multivariate Komplexitatsanalysen von Algorithmischen Herausforderungen in Fairness und Nachhaltigkeit /
Author:	Kellerhals, Leon,
Description:	1 electronic resource (218 pages)
Notes:	Source: Dissertations Abstracts International, Volume: 86-08, Section: B.
Contained By:	Dissertations Abstracts International86-08B.
Subject:	Computer science. -
Online resource:	https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=31868643
ISBN:	9798304971683

Multivariate Complexity Analyses for Algorithmic Challenges in Fairness and Sustainability = = Multivariate Komplexitatsanalysen von Algorithmischen Herausforderungen in Fairness und Nachhaltigkeit /
Kellerhals, Leon,

Multivariate Complexity Analyses for Algorithmic Challenges in Fairness and Sustainability =Multivariate Komplexitatsanalysen von Algorithmischen Herausforderungen in Fairness und Nachhaltigkeit /Leon Kellerhals. - 1 electronic resource (218 pages)

Source: Dissertations Abstracts International, Volume: 86-08, Section: B.

This thesis studies selected algorithmic challenges related to the emerging fields of fairness in algorithms and computational sustainability, with a focus on the parameterized complexity of the underlying computational problems. The field of fairness in algorithms deals with problems that are applied to make decisions which have an impact on individuals, with the goal to ensure that no individuals are affected disparately by the decision. The field of computational sustainability deals with problems that arise in our efforts to balance out environmental, economic, and societal needs for a sustainable future. Specifically, we study the following four algorithmic challenges. Modification-Fair Cluster Editing. Standard algorithms for cluster editing (also known as correlation clustering) may output solutions that are discriminatory against some groups, i.e., by having most modifications incident to one group. We propose a fairness concept with the goal to keep the number of edits incident to each group proportional to its size. Focusing on the setting with two groups, we show (among other results) that our modification-fair variant of the cluster editing problem is NP-hard even in the restricted case in which one may only insert edges within the groups, while still remaining fixed-parameter tractable with respect to the number of edge edits in its unrestricted form. A preliminary empirical analysis shows that the cost of optimal modification-fair solutions differs from the cost of optimal "non-fair" solutions only by a small percentage.Range-Fair Paths. We consider a general fairness measure which encompasses several existing ones and can be modeled as a matroid. We incorporate this measure into the problem of finding paths in vertex-colored paths, which results in an NP-hard problem. We study said problem in terms of its parameterized complexity, focusing on the canonical parameters number of colors and length of the desired path, as well as on parameters that measure the structural complexity of the given graph. We show, among other results, that there is an algorithm for finding shortest fair paths that runs in polynomial time if there are constantly many colors, and an algorithm for finding fair paths of length l whose running time is single-exponential in l and polynomial in the graph size.Locally Diverse Paths. We next study the problem of finding paths on vertex-colored graphs with a local constraint that prohibits colors to be visited more than once within any subpath of fixed length. Thinking of the time until a color may be revisited as regeneration time of a natural resource or ecosystem, this has applications in preserving biodiversity. Among other results, our thorough fine-grained complexity analysis proves that finding shortest such paths is fixed-parameter tractable with respect to the subpath length. Remarkably, the problem remains tractable even when allowing the paths to take short detours. Placing Green Bridges. Animal habitats are increasingly fragmented due to human-made infrastructure like roads or train tracks. To preserve biodiversity, it is imperative to reconnect such habitats with wildlife crossings, so-called green bridges. We study the problem of finding the best (few) places for green bridges such that the habitat of each animal species is sufficiently connected. In brief, we introduce multiple problem variants that provide different types and grades of connectivity, and study these problems in terms of their classical as well as their parameterized complexity with respect to the number of green bridges and the number of habitats. We also consider the setting in which habitats are structurally restricted. Finally, we provide a preliminary empirical analysis of a selection of our algorithms on real-world graphs.

English

ISBN: 9798304971683Subjects--Topical Terms:

523869
Computer science.
Subjects--Index Terms:

Biodiversity

Multivariate Complexity Analyses for Algorithmic Challenges in Fairness and Sustainability = = Multivariate Komplexitatsanalysen von Algorithmischen Herausforderungen in Fairness und Nachhaltigkeit /
LDR:05354nmm a22003973i 4500 001 2434536
005 20250912102037.5
006 m o d
007 cr|nu||||||||
008 261011s2024 miu||||||m |||||||eng d
020 $a 9798304971683
035 $a (MiAaPQD)AAI31868643
035 $a AAI31868643
040 $a MiAaPQD $b eng $c MiAaPQD $e rda
100 1 $a Kellerhals, Leon, $e author. $3 3824542
245 1 0 $a Multivariate Complexity Analyses for Algorithmic Challenges in Fairness and Sustainability = $b Multivariate Komplexitatsanalysen von Algorithmischen Herausforderungen in Fairness und Nachhaltigkeit / $c Leon Kellerhals.
264 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2024
300 $a 1 electronic resource (218 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertations Abstracts International, Volume: 86-08, Section: B.
500 $a Advisors: Schmid, Stefan; Weller, Mathias Committee members: Bredereck, Robert; Chierichetti, Flavio; Fernau, Henning.
502 $b Dr.Nat. $c Technische Universitaet Berlin (Germany) $d 2024.
520 $a This thesis studies selected algorithmic challenges related to the emerging fields of fairness in algorithms and computational sustainability, with a focus on the parameterized complexity of the underlying computational problems. The field of fairness in algorithms deals with problems that are applied to make decisions which have an impact on individuals, with the goal to ensure that no individuals are affected disparately by the decision. The field of computational sustainability deals with problems that arise in our efforts to balance out environmental, economic, and societal needs for a sustainable future. Specifically, we study the following four algorithmic challenges. Modification-Fair Cluster Editing. Standard algorithms for cluster editing (also known as correlation clustering) may output solutions that are discriminatory against some groups, i.e., by having most modifications incident to one group. We propose a fairness concept with the goal to keep the number of edits incident to each group proportional to its size. Focusing on the setting with two groups, we show (among other results) that our modification-fair variant of the cluster editing problem is NP-hard even in the restricted case in which one may only insert edges within the groups, while still remaining fixed-parameter tractable with respect to the number of edge edits in its unrestricted form. A preliminary empirical analysis shows that the cost of optimal modification-fair solutions differs from the cost of optimal "non-fair" solutions only by a small percentage.Range-Fair Paths. We consider a general fairness measure which encompasses several existing ones and can be modeled as a matroid. We incorporate this measure into the problem of finding paths in vertex-colored paths, which results in an NP-hard problem. We study said problem in terms of its parameterized complexity, focusing on the canonical parameters number of colors and length of the desired path, as well as on parameters that measure the structural complexity of the given graph. We show, among other results, that there is an algorithm for finding shortest fair paths that runs in polynomial time if there are constantly many colors, and an algorithm for finding fair paths of length l whose running time is single-exponential in l and polynomial in the graph size.Locally Diverse Paths. We next study the problem of finding paths on vertex-colored graphs with a local constraint that prohibits colors to be visited more than once within any subpath of fixed length. Thinking of the time until a color may be revisited as regeneration time of a natural resource or ecosystem, this has applications in preserving biodiversity. Among other results, our thorough fine-grained complexity analysis proves that finding shortest such paths is fixed-parameter tractable with respect to the subpath length. Remarkably, the problem remains tractable even when allowing the paths to take short detours. Placing Green Bridges. Animal habitats are increasingly fragmented due to human-made infrastructure like roads or train tracks. To preserve biodiversity, it is imperative to reconnect such habitats with wildlife crossings, so-called green bridges. We study the problem of finding the best (few) places for green bridges such that the habitat of each animal species is sufficiently connected. In brief, we introduce multiple problem variants that provide different types and grades of connectivity, and study these problems in terms of their classical as well as their parameterized complexity with respect to the number of green bridges and the number of habitats. We also consider the setting in which habitats are structurally restricted. Finally, we provide a preliminary empirical analysis of a selection of our algorithms on real-world graphs.
546 $a English
590 $a School code: 1119
650 4 $a Computer science. $3 523869
650 4 $a Graphs. $3 3685259
650 4 $a Biodiversity. $3 627066
650 4 $a Connectivity. $3 3560754
650 4 $a Habitats. $3 3564192
650 4 $a Bridges. $3 868720
653 $a Biodiversity
653 $a Computational problems
690 $a 0984
690 $a 0800
710 2 $a Technische Universitaet Berlin (Germany). $e degree granting institution. $3 3819406
720 1 $a Schmid, Stefan $e degree supervisor.
720 1 $a Weller, Mathias $e degree supervisor.
773 0 $t Dissertations Abstracts International $g 86-08B.
790 $a 1119
791 $a Dr.Nat.
792 $a 2024
856 4 0 $u https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=31868643