Exploiting Structure In Computationally Hard Voting Problems

Download Exploiting Structure In Computationally Hard Voting Problems full books in PDF, epub, and Kindle. Read online Exploiting Structure In Computationally Hard Voting Problems ebook anywhere anytime directly on your device. Fast Download speed and no annoying ads. We cannot guarantee that every ebooks is available!

Exploiting structure in computationally hard voting problems

Author : Chen, Jiehua
Publisher : Universitätsverlag der TU Berlin
ISBN 13 : 3798328250
Total Pages : 289 pages
Book Rating : 4.7/5 (983 download)

DOWNLOAD NOW!

Book Synopsis Exploiting structure in computationally hard voting problems by : Chen, Jiehua

Download or read book Exploiting structure in computationally hard voting problems written by Chen, Jiehua and published by Universitätsverlag der TU Berlin. This book was released on 2016-11-11 with total page 289 pages. Available in PDF, EPUB and Kindle. Book excerpt: This thesis explores and exploits structure inherent in voting problems. Some of these structures are found in the preferences of the voters, such as the domain restrictions which have been widely studied in social choice theory [ASS02, ASS10]. Others can be expressed as quantifiable measures (or parameters) of the input, which make them accessible to a parameterized complexity analysis [Cyg+15, DF13, FG06, Nie06]. Accordingly, the thesis deals with two major topics. The first topic revolves around preference structures, e.g. single-crossing or one-dimensional Euclidean structures. It is covered in Chapters 3 to 5. The second topic includes the parameterized complexity analysis of two computationally hard voting problems, making use of some of the structural properties studied in the first part of the thesis. It also investigates questions on the computational complexity, both classical and parameterized, of several voting problems for two widely used parliamentary voting rules. It is covered in Chapters 6 to 8. In Chapter 3, we study the single-crossing property which describes a natural order of the voters such that for each pair of alternatives, there are at most two consecutive voters along this order which differ in their relative ordering of the two alternatives. We find finitely many forbidden subprofiles whose absence from a profile is necessary and sufficient for the existence of single-crossingness. Using this result, we can detect single-crossingness without probing every possible order of the voters. We also present an algorithm for the detection of single-crossingness in O(nm2) time via PQ trees [BL76], where n denotes the number of voters and m the number of alternatives. In Chapter 4, we study the one-dimensional Euclidean property which describes an embedding of the alternatives and voters into the real numbers such that every voter prefers alternatives that are embedded closer to him to those which are embedded farther away. We show that, contrary to our results for the single-crossing property, finitely many forbidden subprofiles are not sufficient to characterize the one-dimensional Euclidean property. In Chapter 5, we study the computational question of achieving a certain property, as for instance single-crossingness, by deleting the fewest number of either alternatives or voters. We show that while achieving single-crossingness by deleting the fewest number of voters can be done in polynomial time, it is NP-hard to achieve this if we delete alternatives instead. Both problem variants are NP-hard for the remaining popular properties, such as single-crossingness or value-restriction. All these problems are trivially fixed-parameter tractable for the parameter “number of alternatives to delete” (resp. “number of voters to delete”) because for each studied property there are finitely many forbidden subprofiles whose removal makes a profile possess this property. In Chapter 6, we introduce a combinatorial variant of CONTROL BY ADDING VOTERS. In CONTROL BY ADDING VOTERS as introduced by Bartholdi III, Tovey, and Trick [BTT92], there is a set of unregistered voters (with known preference orders), and the goal is to add the fewest number of unregistered voters to a given profile such that a specific alternative wins. In our new model, we additionally assume that adding a voter means also adding a bundle (that is, a subset) of other voters for free. We focus on two prominent voting rules, the plurality rule and the Condorcet rule. Our problem turns out to be extremely hard; it is NP-hard for even two alternatives. We identify different parameters arising from the combinatorial model and obtain an almost complete picture of the parameterized complexity landscape. For the case where the bundles of voters have a certain structure, our problem remains hard for single-peaked preferences, while it is polynomial-time solvable for single-crossing preferences. In Chapter 7, we investigate how different natural parameters and price function families influence the computational complexity of SHIFT BRIBERY [EFS09], which asks whether it is possible to make a specific alternative win by shifting it higher in the preference orders of some voters. Each shift has a price, and the goal is not to exceed the budget. We obtain both fixed-parameter tractability and parameterized intractability results. We also study the optimization variant of SHIFT BRIBERY which seeks to minimize the budget spent, and present an approximation algorithm which approximates the budget within a factor of (1 + epsilon) and has a running time whose super-polynomial part depends only on the approximation parameter epsilon and the parameter “number of voters”. In Chapter 8, we turn our focus to two prominent parliamentary voting rules, the successive rule and the amendment rule. Both rules proceed according to a linear order of the alternatives, called the agenda. We investigate MANIPULATION (which asks to add the fewest number of voters with arbitrary preference orders to make a specific alternative win), AGENDA CONTROL (which asks to design an appropriate agenda for a specific alternative to win), and POSSIBLE/NECESSARY WINNER (which asks whether a specific alternative wins in a/every completion of the profile and the agenda). We show that while MANIPULATION and AGENDA CONTROL are polynomial-time solvable for both rules, our real-world experimental results indicate that most profiles cannot be manipulated by only few voters, and that a successful agenda control is typically impossible. POSSIBLE WINNER is NP-hard for both rules. While NECESSARY WINNER is coNP-hard for the amendment rule, it is polynomial-time solvable for the successive rule. All considered computationally hard voting problems are fixed-parameter tractable for the parameter “number of alternatives”. Die vorliegende Arbeit beschäftigt sich mit Wahlproblemen und den darin auftretenden Strukturen. Einige dieser Strukturen finden sich in den Wählerpräferenzen,wie zum Beispiel die in der Sozialwahltheorie (engl. social choice theory) intensiv erforschten domain restrictions [ASS02, ASS10], wo die Wählerpräferenzen eine bestimmte eingeschränkte Struktur haben. Andere Strukturen lassen sich wiederum mittels Problemparametern quantitativ ausdrücken, was sie einer parametrisierten Komplexitätsanalyse zugänglich macht [Cyg+15, DF13, FG06, Nie06]. Dieser Zweiteilung folgend ist die Arbeit in zwei Themengebiete untergliedert. Das erste Gebiet beinhaltet Betrachtungen zu Strukturen in Wählerpräferenzen, wie z. B. Single-Crossing-Strukturen oder eindimensionale euklidische Strukturen. Es wird in den Kapiteln 3 bis 5 abgehandelt. Das zweite Themengebiet umfasst die parametrisierte Komplexitätsanalyse zweier NP-schwerer Wahlprobleme, wobei die neu gewonnenen Erkenntnisse zu den im ersten Teil der Arbeit untersuchten Strukturen verwendet werden. Es beschäftigt sich außerdem mit Fragen sowohl zur klassischen als auch zur parametrisierten Komplexität mehrerer Wahlprobleme für zwei in der Praxis weit verbreitete parlamentarische Wahlverfahren. Dieser Teil der Arbeit erstreckt sich über die Kapitel 6 bis 8. Kapitel 3 untersucht die Single-Crossing-Eigenschaft. Diese beschreibt eine Anordnung der Wähler, bei der es für jedes Paar von Alternativen höchstens zwei aufeinanderfolgende Wähler gibt, die unterschiedlicher Meinung über die Reihenfolge dieser beiden Alternativen sind. Wie sich herausstellt, lässt sich diese Eigenschaft durch eine endliche Anzahl von verbotenen Strukturen charakterisieren. Ein Wählerprofil ist genau dann single-crossing, wenn es keine dieser Strukturen beinhaltet. Es wird außerdem ein Algorithmus vorgestellt, der die Single-Crossing-Eigenschaft unter Verwendung von PQ trees [BL76] in O(nm2) Schritten erkennt, wobei n die Anzahl der Wähler und m die Anzahl der Alternativen ist. Kapitel 4 behandelt Wählerprofile, die eindimensional-euklidisch sind, d.h. für die sich die Alternativen und Wähler so auf die reelle Achse abbilden lassen, dass für jeden Wähler und je zwei Alternativen diejenige näher zum Wähler abgebildet wird, die er der anderen vorzieht. Es stellt sich heraus, dass es im Gegensatz zur Single-Crossing-Eigenschaft nicht möglich ist, eindimensionale euklidische Profile durch endlich viele verbotene Strukturen zu charakterisieren. Kapitel 5 beschäftigt sich mit der Frage, wie berechnungsschwer es ist, eine bestimmte strukturelle Eigenschaft wie z.B. die Single-Crossing-Eigenschaft zu erreichen, indem man eine möglichst kleine Anzahl von Wählern oder Kandidaten aus einem Profil entfernt. Es zeigt sich, dass dieses Problem für die Single-Crossing-Eigenschaft durch das Löschen von Wählern zwar in polynomieller Zeit gelöst werden kann, es durch das Löschen von Kandidaten jedoch NP-schwer ist. Für alle anderen Eigenschaften sind beide Löschensvarianten ebenfalls NP-schwer. Allerdings lässt sich für jedes der Probleme auf triviale Weise mittels des Parameters „Anzahl der zu löschenden Wähler bzw. Alternativen“ fixed-parameter tractability zeigen. Das bedeutet, dass sie effizient lösbar sind, wenn der Parameter klein ist. Der Grund dafür ist, dass sich alle hier betrachteten Eigenschaften durch eine endliche Anzahl verbotener Strukturen charakterisieren lassen, deren Zerstörung die gewünschte Eigenschaft herstellt. Kapitel 6 führt die kombinatorische Variante des bekannten Problems CONTROL BY ADDING VOTERS ein, das erstmals durch Bartholdi III, Tovey und Trick [BTT92] beschrieben wurde. In der klassischen Problemstellung gibt es eine Menge von nichtregistrierten Wählern mit bekannten Präferenzen, und es wird eine kleinste Teilmenge von nichtregistrierten Wählern gesucht, sodass deren Hinzufügen zu einem gegebenen Profil einen bestimmten Kandidaten zum Gewinner macht. In der hier beschriebenen Variante wird zusätzlich angenommen, dass für jeden hinzugefügten Wähler auch eine Menge von weiteren Wählern „kostenlos“ hinzugefügt werden kann. Dieses Problem wird für die beiden bekannten Wahlregeln Condorcet-Wahl und Mehrheitswahl untersucht. Wie sich herausstellt, ist die Problemstellung schon für zwei Alternativen NP-schwer. Desweiteren werden Parameter identifiziert, die sich aus den kombinatorischen Eigenschaften dieses Problems ergeben. Für diese lässt sich eine beinahe erschöpfende Beschreibung der parametrisierten Komplexität des Problems erstellen. In einem Fall, bleibt unser Problem für sogenannte Single-Peaked-Präferenzen berechnungsschwer, während es für Single-Crossing-Präferenzen in polynomieller Zeit lösbar ist. Kapitel 7 untersucht, wie verschiedene natürliche Parameter und Preisfunktionen die Berechnungskomplexität des SHIFT BRIBERY-Problems [EFS09] beeiniv flussen. Darin fragt man, ob eine gegebene Alternative zum Gewinner gemacht werden kann, indem sie in den Präferenzen einiger Wähler nach vorne verschoben wird. Jede Verschiebung hat einen Preis, und das Ziel ist es, ein gegegebenes Budget nicht zu überschreiten. Die Ergebnisse sind gemischt: einige Parameter erlauben effiziente Algorithmen, während für andere das Problem schwer bleibt, z.B. für den Parameter „Anzahl der beeinflussten Wähler“ ist das Problem sogar W[2]-schwer. Für die Optimierungsvariante von SHIFT BRIBERY, bei der das verwendete Budget minimiert wird, erzielen wir einen Approximationsalgorithmus mit einem Approximationsfaktor von (1 + epsilon), dessen Laufzeit in ihrem nicht-polynomiellen Anteil nur von epsilon und der Anzahl der Wähler abhängt. Kapitel 8 konzentriert sich auf zwei weitverbreitete parlamentarische Wahlregeln: die successive rule und die amendment rule. Beide Regeln verwenden eine lineare Ordnung der Alternativen, auch Agenda genannt. Es werden drei Probleme untersucht: MANIPULATION fragt nach der kleinstmöglichen Anzahl von Wählern mit beliebigen Präferenzen, deren Hinzufügung einen bestimmten Kandidaten zum Gewinner macht; AGENDA CONTROL fragt, ob es möglich ist, eine Agenda derart festzulegen, dass ein bestimmter Kandidat gewinnt; POSSIBLE/NECESSARY WINNER fragt für unvollständige Wählerpräferenzen und/oder eine nur teilweise festgelegte Agenda, ob eine bestimmte Alternative überhaupt bzw. sicher zum Sieger machen kann. Es stellt sich heraus, dass sowohl MANIPULATION als auch AGENDA CONTROL für beide Wahlregeln in polynomieller Zeit lösbar sind. Allerdings deuten die Ergebnisse einer auf realem Wählerverhalten basierenden, experimentellen Studie darauf hin, dass die meisten Profile nicht durch einige wenige Wähler manipuliert werden können, und dass eine erfolgreiche Kontrolle mittels Agenda typischerweise nicht möglich ist. POSSIBLE WINNER ist für beide Regeln NP-schwer, während NECESSARY WINNER für die amendment rule coNP-schwer und für die successive rule in polynomieller Zeit lösbar ist. Alle betrachtete NP-schwere oder coNP-schwere Wahlprobleme sind „fixed-parameter tractable“ für den Parameter „Anzahl der Alternativen“.

Algorithmic aspects of resource allocation and multiwinner voting: theory and experiments

Author : Kaczmarczyk, Andrzej
Publisher : Universitätsverlag der TU Berlin
ISBN 13 : 3798332150
Total Pages : 248 pages
Book Rating : 4.7/5 (983 download)

DOWNLOAD NOW!

Book Synopsis Algorithmic aspects of resource allocation and multiwinner voting: theory and experiments by : Kaczmarczyk, Andrzej

Download or read book Algorithmic aspects of resource allocation and multiwinner voting: theory and experiments written by Kaczmarczyk, Andrzej and published by Universitätsverlag der TU Berlin. This book was released on 2021-12-10 with total page 248 pages. Available in PDF, EPUB and Kindle. Book excerpt: This thesis is concerned with investigating elements of computational social choice in the light of real-world applications. We contribute to a better understanding of the areas of fair allocation and multiwinner voting. For both areas, inspired by real-world scenarios, we propose several new notions and extensions of existing models. Then, we analyze the complexity of answering the computational questions raised by the introduced concepts. To this end, we look through the lens of parameterized complexity. We identify different parameters which describe natural features specific to the computational problems we investigate. Exploiting the parameters, we successfully develop efficient algorithms for spe- cific cases of the studied problems. We complement our analysis by showing which parameters presumably cannot be utilized for seeking efficient algorithms. Thereby, we provide comprehensive pictures of the computational complexity of the studied problems. Specifically, we concentrate on four topics that we present below, grouped by our two areas of interest. For all but one topic, we present experimental studies based on implementations of newly developed algorithms. We first focus on fair allocation of indivisible resources. In this setting, we consider a collection of indivisible resources and a group of agents. Each agent reports its utility evaluation of every resource and the task is to “fairly” allocate the resources such that each resource is allocated to at most one agent. We concentrate on the two following issues regarding this scenario. The social context in fair allocation of indivisible resources. In many fair allocation settings, it is unlikely that every agent knows all other agents. For example, consider a scenario where the agents represent employees of a large corporation. It is highly unlikely that every employee knows every other employee. Motivated by such settings, we come up with a new model of graph envy-freeness by adapting the classical envy-freeness notion to account for social relations of agents modeled as social networks. We show that if the given social network of agents is simple (for example, if it is a directed acyclic graph), then indeed we can sometimes find fair allocations efficiently. However, we contrast tractability results with showing NP-hardness for several cases, including those in which the given social network has a constant degree. Fair allocations among few agents with bounded rationality. Bounded rationality is the idea that humans, due to cognitive limitations, tend to simplify problems that they face. One of its emanations is that human agents usually tend to report simple utilities over the resources that they want to allocate; for example, agents may categorize the available resources only into two groups of desirable and undesirable ones. Applying techniques for solving integer linear programs, we show that exploiting bounded rationality leads to efficient algorithms for finding envy-free and Pareto-efficient allocations, assuming a small number of agents. Further, we demonstrate that our result actually forms a framework that can be applied to a number of different fairness concepts like envy-freeness up to one good or envy-freeness up to any good. This way, we obtain efficient algorithms for a number of fair allocation problems (assuming few agents with bounded rationality). We also empirically show that our technique is applicable in practice. Further, we study multiwinner voting, where we are given a collection of voters and their preferences over a set of candidates. The outcome of a multiwinner voting rule is a group (or a set of groups in case of ties) of candidates that reflect the voters’ preferences best according to some objective. In this context, we investigate the following themes. The robustness of election outcomes. We study how robust outcomes of multiwinner elections are against possible mistakes made by voters. Assuming that each voter casts a ballot in a form of a ranking of candidates, we represent a mistake by a swap of adjacent candidates in a ballot. We find that for rules such as SNTV, k-Approval, and k-Borda, it is computationally easy to find the minimum number of swaps resulting in a change of an outcome. This task is, however, NP-hard for STV and the Chamberlin-Courant rule. We conclude our study of robustness with experimentally studying the average number of random swaps leading to a change of an outcome for several rules. Strategic voting in multiwinner elections. We ask whether a given group of cooperating voters can manipulate an election outcome in a favorable way. We focus on the k-Approval voting rule and we show that the computational complexity of answering the posed question has a rich structure. We spot several cases for which our problem is polynomial-time solvable. However, we also identify NP-hard cases. For several of them, we show how to circumvent the hardness by fixed-parameter tractability. We also present experimental studies indicating that our algorithms are applicable in practice. Diese Arbeit befasst sich mit der Untersuchung von Themen des Forschungsgebiets Computational Social Choice im Lichte realer Anwendungen. Dabei trägt sie zu einem besseren Verständnis der Bereiche der fairen Zuordnung und der Mehrgewinnerwahlen bei. Für beide Konzepte schlagen wir – inspiriert von realen Anwendungen – verschiedene neue Begriffe und Erweiterungen bestehender Modelle vor. Anschließend analysieren wir die Komplexität der Beantwortung von Berechnungsfragen, die durch die eingeführten Konzepte aufgeworfen werden. Dabei fokussieren wir uns auf die parametrisierte Komplexität. Hierzu identifizieren wir verschiedene Parameter, welche natürliche Merkmale der von uns untersuchten Berechnungsprobleme beschreiben. Durch die Nutzung dieser Parameter entwickeln wir erfolgreich effiziente Algorithmen für Spezialfälle der untersuchten Probleme. Wir ergänzen unsere Analyse indem wir zeigen, welche Parameter vermutlich nicht verwendet werden können um effiziente Algorithmen zu finden. Dabei zeichnen wir ein umfassendes Bild der Berechnungskomplexität der untersuchten Probleme. Insbesondere konzentrieren wir uns auf vier Themen, die wir, gruppiert nach unseren beiden Schwerpunkten, unten vorstellen. Für alle Themen bis auf eines präsentieren wir Experimente, die auf Implementierungen der von uns neu entwickelten Algorithmen basieren. Wir konzentrieren uns zunächst auf die faire Zuordnung unteilbarer Ressourcen. Hier betrachten wir eine Menge unteilbarer Ressourcen und eine Gruppe von Agenten. Jeder Agent gibt eine Bewertung des Nutzens jeder Ressource ab und die Aufgabe besteht darin, eine "faire" Zuordnung der Ressourcen zu finden, wobei jede Ressource höchstens einem Agenten zugeordnet werden kann. Innerhalb dieses Bereiches konzentrieren wir uns auf die beiden folgenden Problemstellungen. Der soziale Kontext bei der fairen Zuordnung unteilbarer Ressourcen. In vielen Szenarien, in denen Ressourcen zugeordnet werden sollen, ist es unwahrscheinlich, dass jeder Agent alle anderen kennt. Vorstellbar ist beispielsweise ein Szenario, in dem die Agenten Mitarbeiter eines großen Unternehmens repräsentieren. Es ist höchst unwahrscheinlich, dass jeder Mitarbeiter jeden anderen Mitarbeiter kennt. Motiviert durch solche Szenarien entwickeln wir ein neues Modell der graph-basierten Neidfreiheit. Wir erweitern den klassischen Neidfreiheitsbegriff um die sozialen Beziehungen von Agenten, die durch soziale Netzwerke modelliert werden. Einerseits zeigen wir, dass wenn das soziale Netzwerk der Agenten einfach ist (zum Beispiel, wenn es sich um einen gerichteten azyklischen Graph handelt), in manchen Fällen faire Zuordnungen effizient gefunden werden können. Andererseits stellen wir diesen algorithmisch positiven Ergebnissen mehrere NP-schweren Fällen entgegen. Ein Beispiel für einen solchen Fall sind soziale Netzwerke mit einem konstanten Knotengrad. Faire Zuteilung an wenige Agenten mit begrenzter Rationalität. Begrenzte Rationalität beschreibt die Idee, dass Menschen aufgrund kognitiver Grenzen dazu neigen, Probleme, mit denen sie konfrontiert werden, zu vereinfachen. Eine mögliche Folge dieser Grenzen ist, dass menschliche Agenten in der Regel einfache Bewertungen der gewünschten Ressourcen abgeben; beispielsweise könnten Agenten die verfügbaren Ressourcen nur in zwei Gruppen, erwünschte und unerwünschte Ressourcen, kategorisieren. Durch Anwendung von Techniken zum Lösen von Ganzzahligen Linearen Programmen zeigen wir, dass unter der Annahme einer kleinen Anzahl von Agenten die Ausnutzung begrenzter Rationalität dabei hilft, effiziente Algorithmen zum Finden neidfreier und Pareto-effizienter Zuweisungen zu entwickeln. Weiterhin zeigen wir, dass unser Ergebnis ein allgemeines Verfahren liefert, welches auf eine Reihe verschiedener Fairnesskonzepte angewendet werden kann, wie zum Beispiel Neidfreiheit bis auf ein Gut oder Neidfreiheit bis auf irgendein Gut. Auf diese Weise gewinnen wir effiziente Algorithmen für eine Reihe fairer Zuordnungsprobleme (wenige Agenten mit begrenzter Rationalität vorausgesetzt). Darüber hinaus zeigen wir empirisch, dass unsere Technik in der Praxis anwendbar ist. Weiterhin untersuchen wir Mehrgewinnerwahlen, bei denen uns eine Menge von Wählern sowie ihre Präferenzen über eine Reihe von Kandidaten gegeben sind. Das Ergebnis eines Mehrgewinnerwahlverfahrens ist eine Gruppe (oder eine Menge von Gruppen im Falle eines Unentschiedens) von Kandidaten, welche die Präferenzen der Wähler am besten einem bestimmten Ziel folgend widerspiegeln. In diesem Kontext untersuchen wir die folgenden Themen. Die Robustheit von Wahlergebnissen. Wir untersuchen, wie robust die Ergebnisse von Mehrgewinnerwahlen gegenüber möglicher Fehler der Wähler sind. Unter der Annahme, dass jeder Wähler eine Stimme in Form einer Rangliste von Kandidaten abgibt, modellieren wir einen Fehler als einen Tausch benachbarter Kandidaten in der Rangliste. Wir zeigen, dass für Wahlregeln wie SNTV, k-Approval und k-Borda die minimale Anzahl an Vertauschungen, welche zu einer Ergebnisänderung führt, einfach zu berechnen ist. Für STV und die Chamberlin-Courant-Regel ist diese Aufgabe allerdings NP-schwer. Wir schließen unsere Untersuchung der Robustheit unterschiedlicher Wahlregeln ab mit einer experimentellen Evaluierung der durchschnittlichen Anzahl zufälliger Vertauschungen, die zu einer Änderung des Ergebnisses führen. Strategische Abstimmung bei Wahlen mit mehreren Gewinnern. Wir fragen, ob eine bestimmte Gruppe von kooperierenden Wählern ein Wahlergebnis zu ihren Gunsten manipulieren kann. Dabei konzentrieren wir uns auf die k-Approval-Wahlregel. Wir zeigen, dass die Berechnungskomplexität der besagten Manipulation eine reiche Struktur besitzt. Auf der einen Seite identifizieren wir mehrere Fälle in denen das Problem in Polynomzeit lösbar ist. Auf der anderen Seite identifizieren wir jedoch auch NP-schwere Fälle. Für einige von ihnen zeigen wir, wie die Berechnungsschwere durch parametrisierte Algorithmen umgangen werden kann. Wir präsentieren zudem experimentelle Untersuchungen, welche darauf hindeuten, dass unsere Algorithmen in der Praxis anwendbar sind.

Classic graph problems made temporal – a parameterized complexity analysis

Author : Molter, Hendrik
Publisher : Universitätsverlag der TU Berlin
ISBN 13 : 3798331723
Total Pages : 227 pages
Book Rating : 4.7/5 (983 download)

DOWNLOAD NOW!

Book Synopsis Classic graph problems made temporal – a parameterized complexity analysis by : Molter, Hendrik

Download or read book Classic graph problems made temporal – a parameterized complexity analysis written by Molter, Hendrik and published by Universitätsverlag der TU Berlin. This book was released on 2020 with total page 227 pages. Available in PDF, EPUB and Kindle. Book excerpt: This thesis investigates the parameterized computational complexity of six classic graph problems lifted to a temporal setting. More specifically, we consider problems defined on temporal graphs, that is, a graph where the edge set may change over a discrete time interval, while the vertex set remains unchanged. Temporal graphs are well-suited to model dynamic data and hence they are naturally motivated in contexts where dynamic changes or time-dependent interactions play an important role, such as, for example, communication networks, social networks, or physical proximity networks. The most important selection criteria for our problems was that they are well-motivated in the context of dynamic data analysis. Since temporal graphs are mathematically more complex than static graphs, it is maybe not surprising that all problems we consider in this thesis are NP-hard. We focus on the development of exact algorithms, where our goal is to obtain fixed-parameter tractability results, and refined computational hardness reductions that either show NP-hardness for very restricted input instances or parameterized hardness with respect to “large” parameters. In the context of temporal graphs, we mostly consider structural parameters of the underlying graph, that is, the graph obtained by ignoring all time information. However, we also consider parameters of other types, such as ones trying to measure how fast the temporal graph changes over time. In the following we briefly discuss the problem setting and the main results. Restless Temporal Paths. A path in a temporal graph has to respect causality, or time, which means that the edges used by a temporal path have to appear at non-decreasing times. We investigate temporal paths that additionally have a maximum waiting time in every vertex of the temporal graph. Our main contributions are establishing NP-hardness for the problem of finding restless temporal paths even in very restricted cases, and showing W[1]-hardness with respect to the feedback vertex number of the underlying graph. Temporal Separators. A temporal separator is a vertex set that, when removed from the temporal graph, destroys all temporal paths between two dedicated vertices. Our contribution here is twofold: Firstly, we investigate the computational complexity of finding temporal separators in temporal unit interval graphs, a generalization of unit interval graphs to the temporal setting. We show that the problem is NP-hard on temporal unit interval graphs but we identify an additional restriction which makes the problem solvable in polynomial time. We use the latter result to develop a fixed-parameter algorithm with a “distance-to-triviality” parameterization. Secondly, we show that finding temporal separators that destroy all restless temporal paths is Σ-P-2-hard. Temporal Matchings. We introduce a model for matchings in temporal graphs, where, if two vertices are matched at some point in time, then they have to “recharge” afterwards, meaning that they cannot be matched again for a certain number of time steps. In our main result we employ temporal line graphs to show that finding matchings is NP-hard even on instances where the underlying graph is a path. Temporal Coloring. We lift the classic graph coloring problem to the temporal setting. In our model, every edge has to be colored properly (that is,the endpoints are colored differently) at least once in every time interval of a certain length. We show that this problem is NP-hard in very restricted cases, even if we only have two colors. We present simple exponential-time algorithms to solve this problem. As a main contribution, we show that these algorithms presumably cannot be improved significantly. Temporal Cliques and s-Plexes. We propose a model for temporal s-plexes that is a canonical generalization of an existing model for temporal cliques. Our main contribution is a fixed-parameter algorithm that enumerates all maximal temporal s-plexes in a given temporal graph, where we use a temporal adaptation of degeneracy as a parameter. Temporal Cluster Editing. We present a model for cluster editing in temporal graphs, where we want to edit all “layers” of a temporal graph into cluster graphs that are sufficiently similar. Our main contribution is a fixed-parameter algorithm with respect to the parameter “number of edge modifications” plus the “measure of similarity” of the resulting clusterings. We further show that there is an efficient preprocessing procedure that can provably reduce the size of the input instance to be independent of the number of vertices of the original input instance.

Matching minors in bipartite graphs

Author : Wiederrecht, Sebastian
Publisher : Universitätsverlag der TU Berlin
ISBN 13 : 3798332525
Total Pages : 486 pages
Book Rating : 4.7/5 (983 download)

DOWNLOAD NOW!

Book Synopsis Matching minors in bipartite graphs by : Wiederrecht, Sebastian

Download or read book Matching minors in bipartite graphs written by Wiederrecht, Sebastian and published by Universitätsverlag der TU Berlin. This book was released on 2022-04-19 with total page 486 pages. Available in PDF, EPUB and Kindle. Book excerpt: In this thesis we adapt fundamental parts of the Graph Minors series of Robertson and Seymour for the study of matching minors and investigate a connection to the study of directed graphs. We develope matching theoretic to established results of graph minor theory: We characterise the existence of a cross over a conformal cycle by means of a topological property. Furthermore, we develope a theory for perfect matching width, a width parameter for graphs with perfect matchings introduced by Norin. here we show that the disjoint alternating paths problem can be solved in polynomial time on graphs of bounded width. Moreover, we show that every bipartite graph with high perfect matching width must contain a large grid as a matching minor. Finally, we prove an analogue of the we known Flat Wall theorem and provide a qualitative description of all bipartite graphs which exclude a fixed matching minor. In der vorliegenden Arbeit werden fundamentale Teile des Graphminorenprojekts von Robertson und Seymour für das Studium von Matching Minoren adaptiert und Verbindungen zur Strukturtheorie gerichteter Graphen aufgezeigt. Wir entwickeln matchingtheoretische Analogien zu etablierten Resultaten des Graphminorenprojekts: Wir charakterisieren die Existenz eines Kreuzes über einem konformen Kreis mittels topologischer Eigenschaften. Weiter entwickeln wir eine Theorie zu perfekter Matchingweite, einem Weiteparameter für Graphen mit perfekten Matchings, der von Norin eingeführt wurde. Hier zeigen wir, dass das Disjunkte Alternierende Pfade Problem auf bipartiten Graphen mit beschränkter Weite in Polynomialzeit lösbar ist. Weiter zeigen wir, dass jeder bipartite Graph mit hoher perfekter Matchingweite ein großes Gitter als Matchingminor enthalten muss. Schließlich zeigen wir ein Analogon des bekannten Flat Wall Theorem und geben eine qualitative Beschreibung aller bipartiter Graphen an, die einen festen Matching Minor ausschließen.

Fine-grained complexity analysis of some combinatorial data science problems

Author : Froese, Vincent
Publisher : Universitätsverlag der TU Berlin
ISBN 13 : 3798330034
Total Pages : 185 pages
Book Rating : 4.7/5 (983 download)

DOWNLOAD NOW!

Book Synopsis Fine-grained complexity analysis of some combinatorial data science problems by : Froese, Vincent

Download or read book Fine-grained complexity analysis of some combinatorial data science problems written by Froese, Vincent and published by Universitätsverlag der TU Berlin. This book was released on 2018-10-10 with total page 185 pages. Available in PDF, EPUB and Kindle. Book excerpt: This thesis is concerned with analyzing the computational complexity of NP-hard problems related to data science. For most of the problems considered in this thesis, the computational complexity has not been intensively studied before. We focus on the complexity of computing exact problem solutions and conduct a detailed analysis identifying tractable special cases. To this end, we adopt a parameterized viewpoint in which we spot several parameters which describe properties of a specific problem instance that allow to solve the instance efficiently. We develop specialized algorithms whose running times are polynomial if the corresponding parameter value is constant. We also investigate in which cases the problems remain intractable even for small parameter values. We thereby chart the border between tractability and intractability for some practically motivated problems which yields a better understanding of their computational complexity. In particular, we consider the following problems. General Position Subset Selection is the problem to select a maximum number of points in general position from a given set of points in the plane. Point sets in general position are well-studied in geometry and play a role in data visualization. We prove several computational hardness results and show how polynomial-time data reduction can be applied to solve the problem if the sought number of points in general position is very small or very large. The Distinct Vectors problem asks to select a minimum number of columns in a given matrix such that all rows in the selected submatrix are pairwise distinct. This problem is motivated by combinatorial feature selection. We prove a complexity dichotomy with respect to combinations of the minimum and the maximum pairwise Hamming distance of the rows for binary input matrices, thus separating polynomial-time solvable from NP-hard cases. Co-Clustering is a well-known matrix clustering problem in data mining where the goal is to partition a matrix into homogenous submatrices. We conduct an extensive multivariate complexity analysis revealing several NP-hard and some polynomial-time solvable and fixed-parameter tractable cases. The generic F-free Editing problem is a graph modification problem in which a given graph has to be modified by a minimum number of edge modifications such that it does not contain any induced subgraph isomorphic to the graph F. We consider three special cases of this problem: The graph clustering problem Cluster Editing with applications in machine learning, the Triangle Deletion problem which is motivated by network cluster analysis, and Feedback Arc Set in Tournaments with applications in rank aggregation. We introduce a new parameterization by the number of edge modifications above a lower bound derived from a packing of induced forbidden subgraphs and show fixed-parameter tractability for all of the three above problems with respect to this parameter. Moreover, we prove several NP-hardness results for other variants of F-free Editing for a constant parameter value. The problem DTW-Mean is to compute a mean time series of a given sample of time series with respect to the dynamic time warping distance. This is a fundamental problem in time series analysis the complexity of which is unknown. We give an exact exponential-time algorithm for DTW-Mean and prove polynomial-time solvability for the special case of binary time series. Diese Dissertation befasst sich mit der Analyse der Berechnungskomplexität von NP-schweren Problemen aus dem Bereich Data Science. Für die meisten der hier betrachteten Probleme wurde die Berechnungskomplexität bisher nicht sehr detailliert untersucht. Wir führen daher eine genaue Komplexitätsanalyse dieser Probleme durch, mit dem Ziel, effizient lösbare Spezialfälle zu identifizieren. Zu diesem Zweck nehmen wir eine parametrisierte Perspektive ein, bei der wir bestimmte Parameter definieren, welche Eigenschaften einer konkreten Probleminstanz beschreiben, die es ermöglichen, diese Instanz effizient zu lösen. Wir entwickeln dabei spezielle Algorithmen, deren Laufzeit für konstante Parameterwerte polynomiell ist. Darüber hinaus untersuchen wir, in welchen Fällen die Probleme selbst bei kleinen Parameterwerten berechnungsschwer bleiben. Somit skizzieren wir die Grenze zwischen schweren und handhabbaren Probleminstanzen, um ein besseres Verständnis der Berechnungskomplexität für die folgenden praktisch motivierten Probleme zu erlangen. Beim General Position Subset Selection Problem ist eine Menge von Punkten in der Ebene gegeben und das Ziel ist es, möglichst viele Punkte in allgemeiner Lage davon auszuwählen. Punktmengen in allgemeiner Lage sind in der Geometrie gut untersucht und spielen unter anderem im Bereich der Datenvisualisierung eine Rolle. Wir beweisen etliche Härteergebnisse und zeigen, wie das Problem mittels Polynomzeitdatenreduktion gelöst werden kann, falls die Anzahl gesuchter Punkte in allgemeiner Lage sehr klein oder sehr groß ist. Distinct Vectors ist das Problem, möglichst wenige Spalten einer gegebenen Matrix so auszuwählen, dass in der verbleibenden Submatrix alle Zeilen paarweise verschieden sind. Dieses Problem hat Anwendungen im Bereich der kombinatorischen Merkmalsselektion. Wir betrachten Kombinationen aus maximalem und minimalem paarweisen Hamming-Abstand der Zeilenvektoren und beweisen eine Komplexitätsdichotomie für Binärmatrizen, welche die NP-schweren von den polynomzeitlösbaren Kombinationen unterscheidet. Co-Clustering ist ein bekanntes Matrix-Clustering-Problem aus dem Gebiet Data-Mining. Ziel ist es, eine Matrix in möglichst homogene Submatrizen zu partitionieren. Wir führen eine umfangreiche multivariate Komplexitätsanalyse durch, in der wir zahlreiche NP-schwere, sowie polynomzeitlösbare und festparameterhandhabbare Spezialfälle identifizieren. Bei F-free Editing handelt es sich um ein generisches Graphmodifikationsproblem, bei dem ein Graph durch möglichst wenige Kantenmodifikationen so abgeändert werden soll, dass er keinen induzierten Teilgraphen mehr enthält, der isomorph zum Graphen F ist. Wir betrachten die drei folgenden Spezialfälle dieses Problems: Das Graph-Clustering-Problem Cluster Editing aus dem Bereich des Maschinellen Lernens, das Triangle Deletion Problem aus der Netzwerk-Cluster-Analyse und das Problem Feedback Arc Set in Tournaments mit Anwendungen bei der Aggregation von Rankings. Wir betrachten eine neue Parametrisierung mittels der Differenz zwischen der maximalen Anzahl Kantenmodifikationen und einer unteren Schranke, welche durch eine Menge von induzierten Teilgraphen bestimmt ist. Wir zeigen Festparameterhandhabbarkeit der drei obigen Probleme bezüglich dieses Parameters. Darüber hinaus beweisen wir etliche NP-Schwereergebnisse für andere Problemvarianten von F-free Editing bei konstantem Parameterwert. DTW-Mean ist das Problem, eine Durchschnittszeitreihe bezüglich der Dynamic-Time-Warping-Distanz für eine Menge gegebener Zeitreihen zu berechnen. Hierbei handelt es sich um ein grundlegendes Problem der Zeitreihenanalyse, dessen Komplexität bisher unbekannt ist. Wir entwickeln einen exakten Exponentialzeitalgorithmus für DTW-Mean und zeigen, dass der Spezialfall binärer Zeitreihen in polynomieller Zeit lösbar ist.

Dualities in graphs and digraphs

Author : Hatzel, Meike
Publisher : Universitätsverlag der TU Berlin
ISBN 13 : 3798332916
Total Pages : 294 pages
Book Rating : 4.7/5 (983 download)

DOWNLOAD NOW!

Book Synopsis Dualities in graphs and digraphs by : Hatzel, Meike

Download or read book Dualities in graphs and digraphs written by Hatzel, Meike and published by Universitätsverlag der TU Berlin. This book was released on 2023-05-23 with total page 294 pages. Available in PDF, EPUB and Kindle. Book excerpt: In this thesis we describe dualities in directed as well as undirected graphs based on tools such as width-parameters, obstructions and substructures. We mainly focus on directed graphs and their structure. In the context of a long open conjecture that bounds the monotonicity costs of a version of the directed cops and robber game, we introduce new width-measures based on directed separations that are closely related to DAG-width. We identify a tangle-like obstruction for which we prove a duality theorem. Johnson, Reed, Robertson, Seymour and Thomas introduced the width measure directed treewidth as a generalisation of treewidth for directed graphs. We introduce a new width measure, the cyclewidth, which is parametrically equivalent to directed treewidth. Making use of the connection between directed graphs and bipartite graphs with perfect matchings we characterise the digraphs of low cyclewidth. Generalising the seminal work by Robertson and Seymour resulting in a global structure theorem for undirected graphs, there is the goal of obtaining a structure theorem, based on directed treewidth, describing the structure of the directed graphs excluding a fixed butterfly minor. Working in this direction we present a new flat wall theorem for directed graphs which we believe to provide a better base for a directed structure theorem than the existing ones. On undirected graphs we present several results on induced subgraphs in the graphs themselves or the square graph of their linegraph. These results range from general statements about all graphs to the consideration of specific graph classes such as the one with exactly two moplexes. In der vorliegenden Arbeit beschreiben wir Dualitäten in gerichteten sowie in ungerichteten Graphen basierend auf Konzepten wie Weiteparametern, Obstruktionen und Substrukturen. Der Hauptfokus der Arbeit liegt bei gerichteten Graphen und ihrer Struktur. Im Kontext einer lange offenen Vermutung, dass die Monotoniekosten einer Variante des Räuber und Gendarm Spiels für gerichtete Graphen beschränkt sind, führen wir neue Weiteparameter ein, die auf gerichteten Separationen basieren und eng mit DAG-Weite verwandt sind. Wir identifizieren Tangle-artige Obstruktionen zu diesen Weiteparametern und beweisen die Dualität zwischen diesen beiden Konzepten. Johnson, Reed, Robertson, Seymour und Thomas haben die gerichtete Baumweite als gerichtete Verallgemeinerung der Baumweite auf ungerichteten Graphen eingeführt. Wir führen einen neuen Weiteparameter, die Cyclewidth, ein, der parametrisch equivalent zur gerichteten Baumweite ist. Unter Nutzung der Verwandtschaft von gerichteten Graphen und bipartiten Graphen mit perfekten Matchings charakterisieren wir die gerichteten Graphen mit kleiner Cyclewidth. Ein einschlagendes Ergebnis in der Graphenstrukturtheorie ist das Strukturtheorem von Robertson und Seymour. Basierend darauf gibt es Anstrengungen ein solches Strukturtheorem auch für gerichtete Graphen zu finden und dafür die gerichtete Baumweite als Grundlage zu nutzen. Dieses Theorem soll die Struktur aller gerichteten Graphen beschreiben, die einen festen gerichteten Graphen als Butterflyminoren ausschließen. In diesem Kontext beweisen wir ein neues Flat-wall-theorem für gerichtete Graphen, dass unserer Erwartung nach eine bessere Basis für ein gerichtetes Strukturtheorem bietet als die bisher betrachteten Alternativen. Auf ungerichteten Graphen präsentieren wir einige Ergebnisse bezüglich induzierten Subgraphen in gegebenen Graphen oder ihren Linegraphen. Diese Ergebnisse reichen von der Betrachtung spezifischer Graphklassen, wie den Graphen mit zwei Moplexen, bis zu Ergebnissen auf der allgemeinen Klasse aller Graphen.

Elements of dynamic and 2-SAT programming: paths, trees, and cuts

Author : Bentert, Matthias
Publisher : Universitätsverlag der TU Berlin
ISBN 13 : 3798332096
Total Pages : 218 pages
Book Rating : 4.7/5 (983 download)

DOWNLOAD NOW!

Book Synopsis Elements of dynamic and 2-SAT programming: paths, trees, and cuts by : Bentert, Matthias

Download or read book Elements of dynamic and 2-SAT programming: paths, trees, and cuts written by Bentert, Matthias and published by Universitätsverlag der TU Berlin. This book was released on 2021-11-18 with total page 218 pages. Available in PDF, EPUB and Kindle. Book excerpt: In dieser Arbeit entwickeln wir schnellere exakte Algorithmen (schneller bezüglich der Worst-Case-Laufzeit) für Spezialfälle von Graphproblemen. Diese Algorithmen beruhen größtenteils auf dynamischem Programmieren und auf 2-SAT-Programmierung. Dynamisches Programmieren beschreibt den Vorgang, ein Problem rekursiv in Unterprobleme zu zerteilen, sodass diese Unterprobleme gemeinsame Unterunterprobleme haben. Wenn diese Unterprobleme optimal gelöst wurden, dann kombiniert das dynamische Programm diese Lösungen zu einer optimalen Lösung des Ursprungsproblems. 2-SAT-Programmierung bezeichnet den Prozess, ein Problem durch eine Menge von 2-SAT-Formeln (aussagenlogische Formeln in konjunktiver Normalform, wobei jede Klausel aus maximal zwei Literalen besteht) auszudrücken. Dabei müssen erfüllende Wahrheitswertbelegungen für eine Teilmenge der 2-SAT-Formeln zu einer Lösung des Ursprungsproblems korrespondieren. Wenn eine 2-SAT-Formel erfüllbar ist, dann kann eine erfüllende Wahrheitswertbelegung in Linearzeit in der Länge der Formel berechnet werden. Wenn entsprechende 2-SAT-Formeln also in polynomieller Zeit in der Eingabegröße des Ursprungsproblems erstellt werden können, dann kann das Ursprungsproblem in polynomieller Zeit gelöst werden. Im folgenden beschreiben wir die Hauptresultate der Arbeit. Bei dem Diameter-Problem wird die größte Distanz zwischen zwei beliebigen Knoten in einem gegebenen ungerichteten Graphen gesucht. Das Ergebnis (der Durchmesser des Eingabegraphen) gehört zu den wichtigsten Parametern der Graphanalyse. In dieser Arbeit erzielen wir sowohl positive als auch negative Ergebnisse für Diameter. Wir konzentrieren uns dabei auf parametrisierte Algorithmen für Parameterkombinationen, die in vielen praktischen Anwendungen klein sind, und auf Parameter, die eine Distanz zur Trivialität messen. Bei dem Problem Length-Bounded Cut geht es darum, ob es eine Kantenmenge begrenzter Größe in einem Eingabegraphen gibt, sodass das Entfernen dieser Kanten die Distanz zwischen zwei gegebenen Knoten auf ein gegebenes Minimum erhöht. Wir bestätigen in dieser Arbeit eine Vermutung aus der wissenschaftlichen Literatur, dass Length-Bounded Cut in polynomieller Zeit in der Eingabegröße auf Einheitsintervallgraphen (Intervallgraphen, in denen jedes Intervall die gleiche Länge hat) gelöst werden kann. Der Algorithmus basiert auf dynamischem Programmieren. k-Disjoint Shortest Paths beschreibt das Problem, knotendisjunkte Pfade zwischen k gegebenen Knotenpaaren zu suchen, sodass jeder der k Pfade ein kürzester Pfad zwischen den jeweiligen Endknoten ist. Wir beschreiben ein dynamisches Programm mit einer Laufzeit n^O((k+1)!) für dieses Problem, wobei n die Anzahl der Knoten im Eingabegraphen ist. Dies zeigt, dass k-Disjoint Shortest Paths in polynomieller Zeit für jedes konstante k gelöst werden kann, was für über 20 Jahre ein ungelöstes Problem der algorithmischen Graphentheorie war. Das Problem Tree Containment fragt, ob ein gegebener phylogenetischer Baum T in einem gegebenen phylogenetischen Netzwerk N enthalten ist. Ein phylogenetisches Netzwerk (bzw. ein phylogenetischer Baum) ist ein gerichteter azyklischer Graph (bzw. ein gerichteter Baum) mit genau einer Quelle, in dem jeder Knoten höchstens eine ausgehende oder höchstens eine eingehende Kante hat und jedes Blatt eine Beschriftung trägt. Das Problem stammt aus der Bioinformatik aus dem Bereich der Suche nach dem Baums des Lebens (der Geschichte der Artenbildung). Wir führen eine neue Variante des Problems ein, die wir Soft Tree Containment nennen und die bestimmte Unsicherheitsfaktoren berücksichtigt. Wir zeigen mit Hilfe von 2-SAT-Programmierung, dass Soft Tree Containment in polynomieller Zeit gelöst werden kann, wenn N ein phylogenetischer Baum ist, in dem jeweils maximal zwei Blätter die gleiche Beschriftung tragen. Wir ergänzen dieses Ergebnis mit dem Beweis, dass Soft Tree Containment NP-schwer ist, selbst wenn N auf phylogenetische Bäume beschränkt ist, in denen jeweils maximal drei Blätter die gleiche Beschriftung tragen. Abschließend betrachten wir das Problem Reachable Object. Hierbei wird nach einer Sequenz von rationalen Tauschoperationen zwischen Agentinnen gesucht, sodass eine bestimmte Agentin ein bestimmtes Objekt erhält. Eine Tauschoperation ist rational, wenn beide an dem Tausch beteiligten Agentinnen ihr neues Objekt gegenüber dem jeweiligen alten Objekt bevorzugen. Reachable Object ist eine Verallgemeinerung des bekannten und viel untersuchten Problems Housing Market. Hierbei sind die Agentinnen in einem Graphen angeordnet und nur benachbarte Agentinnen können Objekte miteinander tauschen. Wir zeigen, dass Reachable Object NP-schwer ist, selbst wenn jede Agentin maximal drei Objekte gegenüber ihrem Startobjekt bevorzugt und dass Reachable Object polynomzeitlösbar ist, wenn jede Agentin maximal zwei Objekte gegenüber ihrem Startobjekt bevorzugt. Wir geben außerdem einen Polynomzeitalgorithmus für den Spezialfall an, in dem der Graph der Agentinnen ein Kreis ist. Dieser Polynomzeitalgorithmus basiert auf 2-SAT-Programmierung. This thesis presents faster (in terms of worst-case running times) exact algorithms for special cases of graph problems through dynamic programming and 2-SAT programming. Dynamic programming describes the procedure of breaking down a problem recursively into overlapping subproblems, that is, subproblems with common subsubproblems. Given optimal solutions to these subproblems, the dynamic program then combines them into an optimal solution for the original problem. 2-SAT programming refers to the procedure of reducing a problem to a set of 2-SAT formulas, that is, boolean formulas in conjunctive normal form in which each clause contains at most two literals. Computing whether such a formula is satisfiable (and computing a satisfying truth assignment, if one exists) takes linear time in the formula length. Hence, when satisfying truth assignments to some 2-SAT formulas correspond to a solution of the original problem and all formulas can be computed efficiently, that is, in polynomial time in the input size of the original problem, then the original problem can be solved in polynomial time. We next describe our main results. Diameter asks for the maximal distance between any two vertices in a given undirected graph. It is arguably among the most fundamental graph parameters. We provide both positive and negative parameterized results for distance-from-triviality-type parameters and parameter combinations that were observed to be small in real-world applications. In Length-Bounded Cut, we search for a bounded-size set of edges that intersects all paths between two given vertices of at most some given length. We confirm a conjecture from the literature by providing a polynomial-time algorithm for proper interval graphs which is based on dynamic programming. k-Disjoint Shortest Paths is the problem of finding (vertex-)disjoint paths between given vertex terminals such that each of these paths is a shortest path between the respective terminals. Its complexity for constant k > 2 has been an open problem for over 20 years. Using dynamic programming, we show that k-Disjoint Shortest Paths can be solved in polynomial time for each constant k. The problem Tree Containment asks whether a phylogenetic tree T is contained in a phylogenetic network N. A phylogenetic network (or tree) is a leaf-labeled single-source directed acyclic graph (or tree) in which each vertex has in-degree at most one or out-degree at most one. The problem stems from computational biology in the context of the tree of life (the history of speciation). We introduce a particular variant that resembles certain types of uncertainty in the input. We show that if each leaf label occurs at most twice in a phylogenetic tree N, then the problem can be solved in polynomial time and if labels can occur up to three times, then the problem becomes NP-hard. Lastly, Reachable Object is the problem of deciding whether there is a sequence of rational trades of objects among agents such that a given agent can obtain a certain object. A rational trade is a swap of objects between two agents where both agents profit from the swap, that is, they receive objects they prefer over the objects they trade away. This problem can be seen as a natural generalization of the well-known and well-studied Housing Market problem where the agents are arranged in a graph and only neighboring agents can trade objects. We prove a dichotomy result that states that the problem is polynomial-time solvable if each agent prefers at most two objects over its initially held object and it is NP-hard if each agent prefers at most three objects over its initially held object. We also provide a polynomial-time 2-SAT program for the case where the graph of agents is a cycle.

On the feasibility of multi-leader replication in the early tiers

Author : Jungnickel, Tim
Publisher : Universitätsverlag der TU Berlin
ISBN 13 : 3798330018
Total Pages : 196 pages
Book Rating : 4.7/5 (983 download)

DOWNLOAD NOW!

Book Synopsis On the feasibility of multi-leader replication in the early tiers by : Jungnickel, Tim

Download or read book On the feasibility of multi-leader replication in the early tiers written by Jungnickel, Tim and published by Universitätsverlag der TU Berlin. This book was released on 2018-09-27 with total page 196 pages. Available in PDF, EPUB and Kindle. Book excerpt: In traditional service architectures that follow the service statelessness principle, the state is primarily held in the data tier. Here, service operators utilize tailored storage solutions to guarantee the required availability; even though failures can occur at any time. This centralized approach to store and process an application’s state in the data tier implies that outages of the entire tier cannot be tolerated. An alternative approach, which is in focus of this thesis, is to decentralize the processing of state information and to use more stateful components in the early tiers. The possibility to tolerate a temporary outage of an entire tier implies that the application’s state can be manipulated by the remaining tiers without waiting for approval from the unavailable tier. This setup requires multi-leader replication, where every replica can accept writes and forwards the resulting changes to the other replicas. This thesis explores the feasibility of using multi-leader replication to store and process state in a decentralized manner across multiple tiers. To this end, two replication mechanisms, namely Conflict-free Replicated Data Types and Operational Transformation, are under particular investigation. We use and extend both mechanism to demonstrate that the aforementioned decentralization is worth considering when designing a service architecture. The challenges that arise when following our approach go back to fundamental impossibility results in distributed systems research, i.e. the impossibility to achieve a fault-tolerant consensus mechanism in asynchronous systems and the inevitable trade-off between availability and consistency in the presence of failures. With this thesis, we contribute to close the exposed gaps of both results by providing usable alternatives for standard IT services. We exemplify the feasibility of our alternatives with a fully distributed IMAP service and a programming library that provides the necessary extension to utilize our approach in a variety of web-based applications. All contributions of this thesis are based on both theory and practice. In particular, all extensions to the existing multi-leader replication mechanisms were proven to satisfy the necessary properties. Moreover, those extensions were also implemented as prototypical applications and evaluated against the corresponding de facto standard software from the industry. Basierend auf dem “service statelessness principle” ist es üblich, Softwaredienste so zu entwerfen, dass der Zustand des Dienstes primär in einer gekapselten Datenschicht verarbeitet wird. Innerhalb der Datenschicht werden spezielle Lösungen verwendet, um die Verfügbarkeit der Daten sicherzustellen. Dieser zentralisierte Ansatz hat zur Folge, dass ein Ausfall oder eine temporäre Nichtverfügbarkeit der gesamten Datenschicht zwangsweise zur Nichtverfügbarkeit des gesamten Dienstes führt. Ein alternativer Ansatz, welcher in dieser Arbeit erforscht wird, ist die dezentralisierte Speicherung und Verarbeitung der Daten in den darüberliegenden Softwareschichten. Um in diesem Ansatz einen Ausfall der gesamten Datenschicht zu kompensieren, ist es zwingend notwendig, dass die verbleibenden Schichten die eingehenden Anfragen ohne die Bestätigung durch die Datenschicht beantworten können. Hierfür wird eine Replikationsarchitektur benötigt, in der jedes Replikat die Anfragen direkt beantworten kann; die so genannte “multi-leader replication”. In dieser Arbeit werden diese Replikationsarchitekturen verwendet, um den Zustand und die Daten eines Dienstes zu dezentralisieren und über mehrere Schichten zu replizieren. Hierbei werden zwei Mechanismen detaillierter betrachtet: “Conflict-free Replicated Data Types” und “Operational Transformation”. Anschließend werden beide Mechanismen erweitert und hinsichtlich der Verwendbarkeit für den beschriebenen Ansatz geprüft. Als Ergebnis dieser Arbeit wird gezeigt, dass ein dezentralisierter Ansatz mit den vorgestellten Mechanismen in Betracht gezogen werden kann. Die Herausforderungen, die bei der Anwendung dieses Ansatzes entstehen, basieren auf nachweislich unlösbaren Problemen aus der Forschung von Verteilten Systemen. Dazu gehört die Unlösbarkeit von Konsensus und die unausweichliche Abwägung zwischen Verfügbarkeit und Konsistenz in einem verteilten System mit Ausfällen. Diese Arbeit trägt dazu bei, die entstehenden Lücken, welche aus diesen fundamentalen Ergebnissen resultieren, zu schließen und die vorgeschlagenen Lösungen für reale IT Dienste anwendbar zu machen. Dieses wird anhand eines dezentralen IMAP Dienstes und einer Programmierbibliothek für Webanwendungen verdeutlicht. Alle Bestandteile dieser Doktorarbeit verbinden Theorie und Praxis. Alle vorgeschlagenen Erweiterungen für bestehende Replikationssysteme werden in formalen Modellen verifiziert und prototypisch implementiert. Die Implementierungen werden außerdem mit vergleichbarer Standardsoftware, welche dem heutigen Stand der Technik entspricht, in praktischen Experimenten evaluiert.

Parity games, separations, and the modal μ-calculus

Author : Dittmann, Christoph
Publisher : Universitätsverlag der TU Berlin
ISBN 13 : 3798328870
Total Pages : 295 pages
Book Rating : 4.7/5 (983 download)

DOWNLOAD NOW!

Book Synopsis Parity games, separations, and the modal μ-calculus by : Dittmann, Christoph

Download or read book Parity games, separations, and the modal μ-calculus written by Dittmann, Christoph and published by Universitätsverlag der TU Berlin. This book was released on 2017-03-08 with total page 295 pages. Available in PDF, EPUB and Kindle. Book excerpt: The topics of this thesis are the modal μ-calculus and parity games. The modal μ-calculus is a common logic for model-checking in computer science. The model-checking problem of the modal μ-calculus is polynomial time equivalent to solving parity games, a 2-player game on labeled directed graphs. We present the first FPT algorithms (fixed-parameter tractable) for the model-checking problem of the modal μ-calculus on restricted classes of graphs, specifically on classes of bounded Kelly-width or bounded DAG-width. In this process we also prove a general decomposition theorem for the modal μ-calculus and define a useful notion of type for this logic. Then, assuming a class of parity games has a polynomial time algorithm solving it, we consider the problem of extending this algorithm to larger classes of parity games. In particular, we show that joining games, pasting games, or adding single vertices preserves polynomial-time solvability. It follows that parity games can be solved in polynomial time if their underlying undirected graph is a tournament, a complete bipartite graph, or a block graph. In the last chapter we present the first non-trivial formal proof about parity games. We explain a formal proof of positional determinacy of parity games in the proof assistant Isabelle/HOL. Die Themen dieser Dissertation sind der modale μ-Kalkül und Paritätsspiele. Der modale μ-Kalkül ist eine häufig eingesetzte Logik im Bereich des Model-Checkings in der Informatik. Das Model-Checking-Problem des modalen μ-Kalküls ist polynomialzeitäquivalent zum Lösen von Paritätsspielen, einem 2-Spielerspiel auf beschrifteten, gerichteten Graphen. Wir präsentieren die ersten FPT-Algorithmen (fixed-parameter tractable) für das Model-Checking-Problem des modalen μ-Kalküls auf Klassen von Graphen mit beschränkter Kelly-Weite oder beschränkter DAG-Weite. Für diesen Zweck beweisen wir einen allgemeineren Zerlegungssatz für den modalen μ-Kalkül und stellen eine nützliche Definition von Typen für diese Logik vor. Angenommen, eine Klasse von Paritätsspielen hat einen Polynomialzeit-Lösungs-Algorithmus, betrachten wir danach das Problem, diese Klassen zu erweitern auf eine Weise, sodass Polynomialzeit-Lösbarkeit erhalten bleibt. Wir zeigen, dass dies beim Join von Paritätsspielen, beim Pasting und beim Hinzufügen einzelner Knoten der Fall ist. Wir folgern daraus, dass das Lösen von Paritätsspielen in Polynomialzeit möglich ist, falls der unterliegende ungerichtete Graph ein Tournament, ein vollständiger bipartiter Graph oder ein Blockgraph ist. Im letzten Kapitel präsentieren wir den ersten nicht-trivialen formalen Beweis über Paritätsspiele. Wir stellen einen formalen Beweis für die positionale Determiniertheit von Paritätsspielen im Beweis-Assistenten Isabelle/HOL vor.

On the Foundations of Dynamic Coalitions

Author : Arbach, Youssef
Publisher : Universitätsverlag der TU Berlin
ISBN 13 : 3798328560
Total Pages : 193 pages
Book Rating : 4.7/5 (983 download)

DOWNLOAD NOW!

Book Synopsis On the Foundations of Dynamic Coalitions by : Arbach, Youssef

Download or read book On the Foundations of Dynamic Coalitions written by Arbach, Youssef and published by Universitätsverlag der TU Berlin. This book was released on 2016-09-16 with total page 193 pages. Available in PDF, EPUB and Kindle. Book excerpt: Dynamic Coalitions denote a temporary collaboration between different entities to achieve a common goal. A key feature that distinguishes Dynamic Coalitions from static coalitions is Dynamic Membership, where new members can join and others can leave after a coalition is set. This thesis studies workflows in Dynamic Coalitions, by analyzing their features, highlighting their unique characteristics and similarities to other workflows, and investigating their relation with Dynamic Membership. For this purpose, we use the formal model of Event Structures and extend it to faithfully model scenarios taken as use cases from healthcare. Event Structures allow for workflows modeling in general, and for modeling Dynamic Membership in Dynamic Coalitions as well through capturing the join and leave events of members. To this end, we first extend Event Structures with Dynamic Causality to address the dynamic nature of DCs. Dynamic Causality allows some events to change the causal dependencies of other events in a structure. Then, we study the expressive power of the resulting Event Structures and show that they contribute only to a specific kind of changes in workflows, namely the pre-planned changes. Second, we present Evolving Structures in order to support ad-hoc and unforeseen changes in workflows, as required by the use cases. Evolving Structures connect different Event Structures with an evolution relation which allows for changing an Event Structure during a system run. We consider different approaches to model evolution and study their equivalences. Furthermore, we show that the history of a workflow should be preserved in our case of evolution in Dynamic Coalitions, and we allow for extracting changes from an evolution to support Process Learning. Third, to capture the goals of DCs, we equip Evolving Structures with constraints concerning the reachability of a set of events that represents a goal. The former extensions allow for examining the changes and evolutions caused by members, and examining members’ contributions to goal satisfaction, through their join and leave events. Finally, we highlight many modeling features posed as requirements by the domain of our Dynamic-Coalition use cases, namely the healthcare, which are independent from the nature of Dynamic Coalitions, e.g. timing. We examine the literature of Event Structures for supporting such features, and we identify that the notion of Priority is missing in Event Structures. To this end, we add Priority to various kinds of Event Structures from the literature. Furthermore, we study the relation between priority on one side, and conjunctive causality, disjunctive causality, causal ambiguity and various kinds of conflict on the other side. Comparing to Adaptive Workflows, which are concerned with evolutions of workflows that occur as a response to changes, e.g. changes in the business environment or exceptions, this thesis shows that Dynamic-Coalition workflows are not only Adaptive but also Goal-Oriented. Besides, it adds one extra trigger for evolution in workflows—unique to Dynamic Coalitions—namely the join of new members who contribute to goal satisfaction in a Dynamic Coalition. Finally the thesis contributes to bridging the gap in modeling between theory and domain experts by supporting step-by-step modeling applied regularly in healthcare and other domains. Dynamische Koalitionen (DKen) bezeichnen eine temporäre Kollaboration zwischen verschiedenen Entitäten zum Erreichen eines gemeinsamen Ziels. Ein Schüsselaspekt, welcher dynamische Koalitionen von statischen Koalitionen unterscheidet ist die dynamische Mitgliedschaft, durch die neue Mitglieder hinzu- kommen und andere die Koalitionen verlassen können, nachdem sie entstanden ist. Diese Arbeit studiert Workflows in dynamische Koalitionen durch eine Analyse ihrer Eigenschaften, das Herausstellen ihrer einzigartigen Charakteristika und Ähnlichkeiten zu anderen Workflows und durch eine Untersuchung ihrer Beziehung zu dynamischer Mitgliedschaft. In diesem Sinne nutzen wir das formales Model der Ereignisstukturen (ESen) und erweitern es, um Fallstudien aus der Medizin angemessen zu modellieren. ESen erlauben sowohl eine generelle Workflow Modellierung als auch eine Darstellung von Eintritt- und Austrittereignissen von Mitgliedern. Zu diesem Zweck erweitern wir ESen zuerst um Dynamische Kausalität, um die dynamische Natur von DKs abzubilden. Dynamische Kausalität erlaubt bestimmten Ereignissen die kausalen Abhängigkeiten anderer Ereignissen in einer Struktur zu verändern. Dann untersuchen wir die Ausdrucksstärke der resutierenden ESen und zeigen, dass sie nur eine spezifische Art der Veränderung abbilden, die sogenannten vorgeplanten Veränderungen. Als Zweites präsentieren wir Evolving in ESen um ad-hoc- und unvorhergesehene Veränderungen zu unterstützen, wie es durch unsere Fallstudien benötigt wird. Evolving in ESen verbinden verschiedene ESen mit einer Relation, welche eine Veränderung einer ES während eines Ablaufes erlaubt. Wir ziehen verschiedene Ansätze der Modelevolution in Betracht und untersuchen ihre Äquivalenzen. Des Weiteren zeigen wir, dass in unserem Fall der Evolution in DKen die Geschichte eines Workflows erhalten bleiben muss und wir ermöglichen das Extrahieren von Veränderungen einer Evolution, um Process Learning zu unterstützen. Drittens: Um die Ziele von DKen abzubilden, fügen wir den Evolving in ESen mit Einschränkungen bezüglich der Erreichbarkeit einer Menge von Ereignissen hinzu, welche das Ziel repräsentieren. Die genannten Erweiterungen erlauben es sowohl die Änderungen und Evolutionen, die vom Mitgliedern verursacht werden als auch die Beiträge der Mitglieder zur Zielerreichung durch deren Entritt- und Austrittereignissen zu untersuchen. Schlussendlich, stellen wir viele Modellierungseigen- schaften dar, welche von den DK-Fallstudien aus der Medizin benötigt werden und unabhängig von der Natur der DKen sind, wie z.B. Timing. Wir untersuchen die Literatur zu ESen bezüglich Unterstützung für solche Eigenschaften und stellen fest, dass der Begriff Priorität in ESen fehlt. Daher fügen wir Priorität zu verschiedenen ESen aus der Literatur hinzu. Des Weiteren untersuchen wir die Beziehungen von Priorität auf zu Konjunktiver Kausalität, disjunktiver Kausalität, kausal Uneindeutigkeit und verschiedenen Formen von Konflikt. Im Vergleich zu Adaptive Workflows, welche sich mit der Evolution von Workflows beschäftigt, die als Reaktion auf Veränderungen entsteht, wie z.B. Veränderungen im Business Environment oder Exceptions, zeigt diese Arbeit das DKen nicht nur adaptiv sondern auch zielorientiert sind. Außerdem fügt sie einen zusätzlichen Auslöser für Evolution in Workflows hinzu, welcher ausschließlich DKen eigen ist: das Hinzukommen neuer Mitglieder welche zur Ziel- erreichung der DK beitragen. Zuletzt trägt diese Arbeit bei, die Lücke der Modellierung zwischen der Theorie und den Domänenexperten zu überbrücken, in dem sie eine Schritt-für-Schritt Modellierung unterstützt, welche regelmäßig in der Medizin und anderen Bereichen angewand wird.

Event structures with higher-order dynamics

Author : Karcher, David S.
Publisher : Universitätsverlag der TU Berlin
ISBN 13 : 3798329958
Total Pages : 150 pages
Book Rating : 4.7/5 (983 download)

DOWNLOAD NOW!

Book Synopsis Event structures with higher-order dynamics by : Karcher, David S.

Download or read book Event structures with higher-order dynamics written by Karcher, David S. and published by Universitätsverlag der TU Berlin. This book was released on 2019-03-11 with total page 150 pages. Available in PDF, EPUB and Kindle. Book excerpt: Event Structure were introduced in 1979 [18] as a formal model to connect the theory of Petri nets and domain theory. Originally they consisted of atomic non-repeatable events, a binary causal dependency relation, and a binary conflict relation between those events. For a long time various extensions of the original formalism were used to define semantics for other structures such as classes of Petri nets and process calculi.In this thesis the Event Structures (ESs) are considered solely as a declarative modelling tool than as a formalism to define semantics for other structures. In order to model highly dynamic real-world processes (i.e. processes in which occurrences of events may change the dependencies of other events) with a concise model the dynamics must be an inherent part of the modelling formalism. Therefore, the Higher-Order Dynamic-Causality ESs (HDESs) were introduced. They consist of a finite set of atomic non-repeatable events, a causal dependency relation between these events, and a rule-based formalism for events to change the dependencies and the existing rules. This formalism is studied with the respect to its expressive power in comparison to transition systems, some subclasses of HDESs, and to Dynamic Condition Response Graphs (DCR-Graphs). A web tool was created in which HDESs can be defined and explored by executing events, creating the corresponding transition system, or even applying some predefined transformations.Ereignisstrukturen wurden 1979 als formales Modell eingeführt um die Theorie der Petri Netze mit der Theorie der Verbände zu verknüpfen. Ursprünglich bestanden sie aus atomaren nicht wiederholbaren Ereignissen, einer binären kausalen Abhängigkeitsrelation und einer binären Konfliktrelation auf den Ereignissen. Lange Zeit wurden verschiedene Erweiterungen des Ursprungsformalismus genutzt, um Semantiken für andere Strukturen zu definieren (z.B. Klassen von Petri Netzen und Prozesskalkülen). In dieser Arbeit werden Ereignisstrukturen (ESs) als deklarativer Modellierungsformalismus betrachtet und nicht, um Semantiken für andere Strukturen zu definieren. Um hochdynamische Prozesse (also Prozesse, in denen Ereignisse die Abhängigkeiten anderer Ereignisse verändern können) aus der realen Welt in einem präzisen, aber kleinen Modell abbilden zu können, muss die Dynamik inhärenter Bestandteil des Modellierungsformalismus sein. Um dieses leisten zu können, wurden die Higher-Order Dynamic-Causality ESs (HDESs) eingeführt. Sie bestehen aus einer endlichen Menge atomarer und nicht wiederholbarer Ereignisse, einer kausalen Abhängigkeitsrelation auf diesen Ereignissen und einem regelbasierten Formalismus, mit dem Ereignisse die Abhängigkeiten anderer Ereignisse (und auch eben diese Regeln) verändern können. Der Formalismus wird bezüglich seiner Ausdrucksstärke im Vergleich zu Transitionssystemen, zu einigen Unterklassen von HDESs und zu Dynamic Condition Response Graphs (DCR-Graphs) betrachtet. Des Weiteren wird ein Web-Tool vorgestellt, das es ermöglicht, HDESs zu definieren und zu erforschen, indem man Ereignisse ausführt, das zugehörige Transitionssystem erzeugt oder vordefinierte Transformationen anwendet.

Trends in Computational Social Choice

Author : Ulle Endriss
Publisher : Lulu.com
ISBN 13 : 1326912097
Total Pages : 424 pages
Book Rating : 4.3/5 (269 download)

DOWNLOAD NOW!

Book Synopsis Trends in Computational Social Choice by : Ulle Endriss

Download or read book Trends in Computational Social Choice written by Ulle Endriss and published by Lulu.com. This book was released on 2017 with total page 424 pages. Available in PDF, EPUB and Kindle. Book excerpt: Computational social choice is concerned with the design and analysis of methods for collective decision making. It is a research area that is located at the interface of computer science and economics. The central question studied in computational social choice is that of how best to aggregate the individual points of view of several agents, so as to arrive at a reasonable compromise. Examples include tallying the votes cast in an election, aggregating the professional opinions of several experts, and finding a fair manner of dividing a set of resources amongst the members of a group -- Back cover.

SOFSEM 2007: Theory and Practice of Computer Science

Author : Jan van Leeuwen
Publisher : Springer Science & Business Media
ISBN 13 : 3540695060
Total Pages : 955 pages
Book Rating : 4.5/5 (46 download)

DOWNLOAD NOW!

Book Synopsis SOFSEM 2007: Theory and Practice of Computer Science by : Jan van Leeuwen

Download or read book SOFSEM 2007: Theory and Practice of Computer Science written by Jan van Leeuwen and published by Springer Science & Business Media. This book was released on 2007-01-04 with total page 955 pages. Available in PDF, EPUB and Kindle. Book excerpt: This book constitutes the refereed proceedings of the 33rd Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2007, held in Harrachov, Czech Republic in January 2007. The 69 revised full papers, presented together with 11 invited contributions were carefully reviewed and selected from 283 submissions. The papers were organized in four topical tracks.

Handbook of Computational Social Choice

Author : Felix Brandt
Publisher : Cambridge University Press
ISBN 13 : 1107060435
Total Pages : 553 pages
Book Rating : 4.1/5 (7 download)

DOWNLOAD NOW!

Book Synopsis Handbook of Computational Social Choice by : Felix Brandt

Download or read book Handbook of Computational Social Choice written by Felix Brandt and published by Cambridge University Press. This book was released on 2016-04-25 with total page 553 pages. Available in PDF, EPUB and Kindle. Book excerpt: A comprehensive survey of computational aspects of collective decisions for graduate students, researchers, and professionals in computer science and economics.

Optimal Districting and Territory Design

Author : Roger Z. Ríos-Mercado
Publisher : Springer Nature
ISBN 13 : 303034312X
Total Pages : 216 pages
Book Rating : 4.0/5 (33 download)

DOWNLOAD NOW!

Book Synopsis Optimal Districting and Territory Design by : Roger Z. Ríos-Mercado

Download or read book Optimal Districting and Territory Design written by Roger Z. Ríos-Mercado and published by Springer Nature. This book was released on 2020-02-04 with total page 216 pages. Available in PDF, EPUB and Kindle. Book excerpt: This book highlights recent advances in the field of districting, territory design, and zone design. Districting problems deal essentially with tactical decisions, and involve mainly dividing a set of geographic units into clusters or territories subject to some planning requirements. This book presents models, theory, algorithms (exact or heuristic), and applications that would bring research on districting systems up-to-date and define the state-of-the-art. Although papers have addressed real-world problems that require districting or territory division decisions, this is the first comprehensive book that directly addresses these problems. The chapters capture the diverse nature of districting applications, as the book is divided into three different areas of research. Part I covers recent up-to-date surveys on important areas of districting such as police districting, health care districting, and districting algorithms based on computational geometry. Part II focuses on recent advances on theory, modeling, and algorithms including mathematical programming and heuristic approaches, and finally, Part III contains successful applications in real-world districting cases.

The Multivariate Algorithmic Revolution and Beyond

Author : Hans L. Bodlaender
Publisher : Springer
ISBN 13 : 3642308910
Total Pages : 521 pages
Book Rating : 4.6/5 (423 download)

DOWNLOAD NOW!

Book Synopsis The Multivariate Algorithmic Revolution and Beyond by : Hans L. Bodlaender

Download or read book The Multivariate Algorithmic Revolution and Beyond written by Hans L. Bodlaender and published by Springer. This book was released on 2012-06-16 with total page 521 pages. Available in PDF, EPUB and Kindle. Book excerpt: Parameterized complexity is currently a thriving field in complexity theory and algorithm design. A significant part of the success of the field can be attributed to Michael R. Fellows. This Festschrift has been published in honor of Mike Fellows on the occasion of his 60th birthday. It contains 20 papers that showcase the important scientific contributions of this remarkable man, describes the history of the field of parameterized complexity, and also reflects on other parts of Mike Fellows’s unique and broad range of interests, including his work on the popularization of discrete mathematics for young children. The volume contains several surveys that introduce the reader to the field of parameterized complexity and discuss important notions, results, and developments in this field.

Introduction to Discrete Event Simulation and Agent-based Modeling

Author : Theodore T. Allen
Publisher : Springer Science & Business Media
ISBN 13 : 0857291394
Total Pages : 220 pages
Book Rating : 4.8/5 (572 download)

DOWNLOAD NOW!

Book Synopsis Introduction to Discrete Event Simulation and Agent-based Modeling by : Theodore T. Allen

Download or read book Introduction to Discrete Event Simulation and Agent-based Modeling written by Theodore T. Allen and published by Springer Science & Business Media. This book was released on 2011-01-12 with total page 220 pages. Available in PDF, EPUB and Kindle. Book excerpt: Discrete event simulation and agent-based modeling are increasingly recognized as critical for diagnosing and solving process issues in complex systems. Introduction to Discrete Event Simulation and Agent-based Modeling covers the techniques needed for success in all phases of simulation projects. These include: • Definition – The reader will learn how to plan a project and communicate using a charter. • Input analysis – The reader will discover how to determine defensible sample sizes for all needed data collections. They will also learn how to fit distributions to that data. • Simulation – The reader will understand how simulation controllers work, the Monte Carlo (MC) theory behind them, modern verification and validation, and ways to speed up simulation using variation reduction techniques and other methods. • Output analysis – The reader will be able to establish simultaneous intervals on key responses and apply selection and ranking, design of experiments (DOE), and black box optimization to develop defensible improvement recommendations. • Decision support – Methods to inspire creative alternatives are presented, including lean production. Also, over one hundred solved problems are provided and two full case studies, including one on voting machines that received international attention. Introduction to Discrete Event Simulation and Agent-based Modeling demonstrates how simulation can facilitate improvements on the job and in local communities. It allows readers to competently apply technology considered key in many industries and branches of government. It is suitable for undergraduate and graduate students, as well as researchers and other professionals.