Refine
Document Type
- Article (3)
- Doctoral Thesis (2)
- Monograph/Edited Volume (1)
- Master's Thesis (1)
- Postprint (1)
Is part of the Bibliography
- yes (8) (remove)
Keywords
- complexity (8) (remove)
Institute
- Hasso-Plattner-Institut für Digital Engineering gGmbH (2)
- Institut für Informatik und Computational Science (2)
- Hasso-Plattner-Institut für Digital Engineering GmbH (1)
- Humanwissenschaftliche Fakultät (1)
- Institut für Biochemie und Biologie (1)
- Institut für Umweltwissenschaften und Geographie (1)
- Sozialwissenschaften (1)
An instance of the marriage problem is given by a graph G = (A boolean OR B, E), together with, for each vertex of G, a strict preference order over its neighbors. A matching M of G is popular in the marriage instance if M does not lose a head-to-head election against any matching where vertices are voters. Every stable matching is a min-size popular matching; another subclass of popular matchings that always exists and can be easily computed is the set of dominant matchings. A popular matching M is dominant if M wins the head-to-head election against any larger matching. Thus, every dominant matching is a max-size popular matching, and it is known that the set of dominant matchings is the linear image of the set of stable matchings in an auxiliary graph. Results from the literature seem to suggest that stable and dominant matchings behave, from a complexity theory point of view, in a very similar manner within the class of popular matchings. The goal of this paper is to show that there are instead differences in the tractability of stable and dominant matchings and to investigate further their importance for popular matchings. First, we show that it is easy to check if all popular matchings are also stable; however, it is co-NP hard to check if all popular matchings are also dominant. Second, we show how some new and recent hardness results on popular matching problems can be deduced from the NP-hardness of certain problems on stable matchings, also studied in this paper, thus showing that stable matchings can be employed to show not only positive results on popular matchings (as is known) but also most negative ones. Problems for which we show new hardness results include finding a min-size (resp., max-size) popular matching that is not stable (resp., dominant). A known result for which we give a new and simple proof is the NP-hardness of finding a popular matching when G is nonbipartite.
Die fortschreitende Digitalisierung durchzieht immer mehr Lebensbereiche und führt zu immer komplexeren sozio-technischen Systemen. Obwohl diese Systeme zur Lebenserleichterung entwickelt werden, können auch unerwünschte Nebeneffekte entstehen. Ein solcher Nebeneffekt könnte z.B. die Datennutzung aus Fitness-Apps für nachteilige Versicherungsentscheidungen sein. Diese Nebeneffekte manifestieren sich auf allen Ebenen zwischen Individuum und Gesellschaft. Systeme mit zuvor unerwarteten Nebeneffekten können zu sinkender Akzeptanz oder einem Verlust von Vertrauen führen. Da solche Nebeneffekte oft erst im Gebrauch in Erscheinung treten, bedarf es einer besonderen Betrachtung bereits im Konstruktionsprozess. Mit dieser Arbeit soll ein Beitrag geleistet werden, um den Konstruktionsprozess um ein geeignetes Hilfsmittel zur systematischen Reflexion zu ergänzen.
In vorliegender Arbeit wurde ein Analysetool zur Identifikation und Analyse komplexer Interaktionssituationen in Software-Entwicklungsprojekten entwickelt. Komplexe Interaktionssituationen sind von hoher Dynamik geprägt, aus der eine Unvorhersehbarkeit der Ursache-Wirkungs-Beziehungen folgt. Hierdurch können die Akteur*innen die Auswirkungen der eigenen Handlungen nicht mehr überblicken, sondern lediglich im Nachhinein rekonstruieren. Hieraus können sich fehlerhafte Interaktionsverläufe auf vielfältigen Ebenen ergeben und oben genannte Nebeneffekte entstehen. Das Analysetool unterstützt die Konstrukteur*innen in jeder Phase der Entwicklung durch eine angeleitete Reflexion, um potenziell komplexe Interaktionssituationen zu antizipieren und ihnen durch Analyse der möglichen Ursachen der Komplexitätswahrnehmung zu begegnen.
Ausgehend von der Definition für Interaktionskomplexität wurden Item-Indikatoren zur Erfassung komplexer Interaktionssituationen entwickelt, die dann anhand von geeigneten Kriterien für Komplexität analysiert werden. Das Analysetool ist als „Do-It-Yourself“ Fragebogen mit eigenständiger Auswertung aufgebaut. Die Genese des Fragebogens und die Ergebnisse der durchgeführten Evaluation an fünf Softwarentwickler*innen werden dargestellt. Es konnte festgestellt werden, dass das Analysetool bei den Befragten als anwendbar, effektiv und hilfreich wahrgenommen wurde und damit eine hohe Akzeptanz bei der Zielgruppe genießt. Dieser Befund unterstützt die gute Einbindung des Analysetools in den Software-Entwicklungsprozess.
In the stable marriage problem, a set of men and a set of women are given, each of whom has a strictly ordered preference list over the acceptable agents in the opposite class. A matching is called stable if it is not blocked by any pair of agents, who mutually prefer each other to their respective partner. Ties in the preferences allow for three different definitions for a stable matching: weak, strong and super-stability. Besides this, acceptable pairs in the instance can be restricted in their ability of blocking a matching or being part of it, which again generates three categories of restrictions on acceptable pairs. Forced pairs must be in a stable matching, forbidden pairs must not appear in it, and lastly, free pairs cannot block any matching.
Our computational complexity study targets the existence of a stable solution for each of the three stability definitions, in the presence of each of the three types of restricted pairs. We solve all cases that were still open. As a byproduct, we also derive that the maximum size weakly stable matching problem is hard even in very dense graphs, which may be of independent interest.
Der neueste Geist des Kapitalismus beschreibt das heutige Mobilisierungs- und Rechtfertigungsregime, welches uns immer wieder dazu bringt, unsere Arbeitskraft zu verwerten und uns täglich ins kapitalistische Hamsterrad zu begeben. Der alte Geist des Kapitalismus, nach dem Fleiß, Disziplin und Sparsamkeit zum gesellschaftlichen Aufstieg führen, trägt längst nicht mehr. Auch reine Selbstverwirklichung, der Anspruch auf Flexibilität und flache Hierarchien reicht nicht mehr aus, um insbesondere gut qualifizierte Menschen zur Arbeit zu motivieren. Der neueste Geist des Kapitalismus hingegen ist das Produkt der tiefen Subjektivierung und Verinnerlichung des Neoliberalismus.
Es geht um beständige berufliche und private Optimierung sowie ein umfassendes Nutzendenken. Glücklich zu sein, ist nicht mehr nur eine Option, sondern es gibt den normativen Anspruch, glücklich sein zu sollen. Das Leistungsprinzip wird aktiv bejaht und Leistungsgerechtigkeit eingefordert. Die Bewältigung von Komplexität wird zum Metathema. Der Anspruch auf Distinktion, insbesondere auch gegenüber „Minderleisten“ nimmt zu. Die Welt wird zunehmend durch die Brille von Zahlen und Statistiken betrachtet, und Key Performance Indicators werden zu ständigen Wegbegleitern. Das Leben wird, verstärkt durch die sozialen Netzwerke, zunehmend zu einer performativen Bühne, die zugleich dem Networking dient. In der Konsequenz der beständigen Optimierung wird es jedoch immer schwerer, zur Ruhe zu kommen.
Dieser neueste Geist des Kapitalismus, dieser umfassende Optimierungsanspruch, hat jedoch gravierende Konsequenzen. Zu den manifesten Pathologien des neuesten Geistes gehören gestiegene Raten von Depressionen, Burn-out und Angststörungen. Gesellschaftlich spreizt sich die soziale Schere immer mehr anhand der Fähigkeit, Komplexität bewältigen zu können, was viele Verlierer und prekäre Gewinner produziert. Daher wird dieser neueste Geist des Kapitalismus sozialkritisch, künstlerkritisch und ideologiekritisch hinterfragt. Die Rolle der Gewerkschaften als der Zentralinstitution der Sozialkritik, die ein tatsächliches Gegengewicht zum neuesten Geist des Kapitalismus bieten kann, wird kontrovers diskutiert. Und es wird aufgezeigt: chillen ist die neue Subversion.
This study investigates whether number dissimilarities on subject and object DPs facilitate the comprehension of subject-and object-extracted centre-embedded relative clauses in children with Grammatical Specific Language Impairment (G-SLI). We compared the performance of a group of English-speaking children with G-SLI (mean age: 12; 11) with that of two groups of younger typically developing (TD) children, matched on grammar and receptive vocabulary, respectively. All groups were more accurate on subject-extracted relative clauses than object-extracted ones and, crucially, they all showed greater accuracy for sentences with dissimilar number features (i.e., one singular, one plural) on the head noun and the embedded DP. These findings are interpreted in the light of current psycholinguistic models of sentence comprehension in TD children and provide further insight into the linguistic nature of G-SLI.
Population models in ecology are often not good at predictions, even if they are complex and seem to be realistic enough. The reason for this might be that Occam's razor, which is key for minimal models exploring ideas and concepts, has been too uncritically adopted for more realistic models of systems. This can tic models too closely to certain situations, thereby preventing them from predicting the response to new conditions. We therefore advocate a new kind of parsimony to improve the application of Occam's razor. This new parsimony balances two contrasting strategies for avoiding errors in modeling: avoiding inclusion of nonessential factors (false inclusions) and avoiding exclusion of sometimes-important factors (false exclusions). It involves a synthesis of traditional modeling and analysis, used to describe the essentials of mechanistic relationships, with elements that arc included in a model because they have been reported to be or can arguably be assumed to be important under certain conditions. The resulting models should be able to reflect how the internal organization of populations change and thereby generate representations of the novel behavior necessary for complex predictions, including regime shifts.
Evaluation komplexer Systeme
(2015)
Seit von Foerster können wir soziale Systeme als Black Boxes betrachten, zu deren Funktionsweise keine klaren Wenn-Dann-Aussagen möglich erscheinen und deren Operationsweise sich für den Beobachter immer nur sequenziell und sprunghaft – und folglich nie ganzheitlich – darstellt. Jedes Bemühen, ein soziales System tiefgründig verstehen und abbilden zu wollen, kann somit schnell ein Gefühl von Orientierungslosigkeit und Überforderung auslösen – ähnlich, wie während einer Achterbahnfahrt. Für die Evaluationsdebatte resultiert aus dieser Sichtweise die Kernfrage, wie nun also im Rahmen von Evaluationen mit sozialer Komplexität umgegangen werden kann.
An diese Frage anknüpfend stellt der vorliegende Band das Feld der systemischen Therapie- und Beratungsansätze als inspirierenden Fundus vor, aus welchem sich Konzepte, Methoden und Techniken zur Gestaltung von Evaluationsvorhaben ableiten lassen. Aber welche Möglichkeiten und Grenzen offenbaren sich dabei? Lässt sich sozialer Komplexität mit Hilfe dieser Ansätze besser begegnen? Welche Rahmenbedingungen sollten dabei erfüllt sein und wie lassen sich systemische von nicht-systemischen Ansätzen unterscheiden?
Business process models are used within a range of organizational initiatives, where every stakeholder has a unique perspective on a process and demands the respective model. As a consequence, multiple process models capturing the very same business process coexist. Keeping such models in sync is a challenge within an ever changing business environment: once a process is changed, all its models have to be updated. Due to a large number of models and their complex relations, model maintenance becomes error-prone and expensive. Against this background, business process model abstraction emerged as an operation reducing the number of stored process models and facilitating model management. Business process model abstraction is an operation preserving essential process properties and leaving out insignificant details in order to retain information relevant for a particular purpose. Process model abstraction has been addressed by several researchers. The focus of their studies has been on particular use cases and model transformations supporting these use cases. This thesis systematically approaches the problem of business process model abstraction shaping the outcome into a framework. We investigate the current industry demand in abstraction summarizing it in a catalog of business process model abstraction use cases. The thesis focuses on one prominent use case where the user demands a model with coarse-grained activities and overall process ordering constraints. We develop model transformations that support this use case starting with the transformations based on process model structure analysis. Further, abstraction methods considering the semantics of process model elements are investigated. First, we suggest how semantically related activities can be discovered in process models-a barely researched challenge. The thesis validates the designed abstraction methods against sets of industrial process models and discusses the method implementation aspects. Second, we develop a novel model transformation, which combined with the related activity discovery allows flexible non-hierarchical abstraction. In this way this thesis advocates novel model transformations that facilitate business process model management and provides the foundations for innovative tool support.