1,722,131 research outputs found
Exact Exponential-Time Algorithms for Domination Problems in Graphs
No full textThis PhD thesis studies exact exponential-time algorithms for domination problems in graphs. Domination problems in graphs are a special kind of subset problems in graphs. A subset problem in a graph is a problem where one is given a graph G=(V,E), and one is asked whether there exist some subset S of a set of items U in the graph (mostly U is either the vertices V or the edges E) that satisfies certain properties. Domination problems in graphs are subset problems in which there is a domination criterion based on a neighbourhood relation in the graph that decides which elements of U are dominated by a given subset S, and where one of the properties that a solution subset S must satisfy is that S must dominate its complement U\S. The most well-known graph domination problem is the Dominating Set problem where the set U is the set of vertices V of G, a vertex subset S dominates all vertices in G that have a neighbour in S, and one is asked to compute the smallest vertex subset S of V that dominates all vertices in V\S. Other examples of domination problems in graphs are Independent Set, Edge Dominating Set, Total Dominating Set, Red-Blue Dominating Set, Partial Dominating Set, and #Dominating Set. We study exact exponential-time algorithms for these problems. These are algorithms that, when executed, use a number of operations that is exponential in a complexity parameter of the input in the worst case. That is, these algorithms use exponential time. Exact exponential-time algorithms then return an optimal solution to the problem. This in contrast to other fields of algorithm design where one sometimes trades running time for other properties of the algorithm or the returned solution. In this thesis, we also study parameterised algorithms for domination problems in graph on graph decompositions. These are algorithms whose worst-case running times are polynomial in the size of the graph and exponential in the graph-width parameter associated to the graph decomposition. Our study led to faster exact exponential-time algorithms for many well-known graph domination problems. This includes an O(1.4969^n)-time algorithm for Dominating Set, an O(1.2114^n)-time algorithm for Independent Set, an O(1.3226^n)-time algorithm for Edge Dominating Set, an O(1.4969^n)-time algorithm for Total Dominating Set, an O(1.2252^n)-time algorithm for Red-Blue Dominating Set, an O(1.5014^n)-time algorithm for Partial Dominating Set, and an O(1.5002^n)-time algorithm for #Dominating Set. We also obtained faster algorithms for these and many other graph domination problems on some prominent types of graph decompositions: tree decompositions, branch decompositions, and, for some problems, clique decompositions (also called k-expressions). A series of interesting new insights and techniques arose from this study. We mention the techniques of inclusion/exclusion-based branching and extended inclusion/exclusion-based branching. We also mention our generalisation of the fast subset convolution algorithm, which we translated to the setting of state-based dynamic programming algorithms on graph decompositions. This thesis also contains an accessible introduction to the field of exact exponential-time algorithms
Nordic Perspectives on Algorithmic Systems Card Box
No full textThis pdf contains the full materials for Nordic Perspectives on Algorithmic Systems: A Card Box, including an information leaflet, four card decks (settings, methods, metaphors, caveats), and the box itself. Please note that the compilation is not optimized for printing!
The contents of this box were developed to support the creation of games for exploration of algorithmic systems in research and design. The box contains four decks of cards: (1) The Settings deck features different algorithmic systems and contexts where they are used, ranging from mainstream platforms like Facebook and Spotify to more particular uses such the allocation of healthcare, the coordination of education work, and facilitation of job seeking. (2) The Methods deck introduces a range of methods that can be used in studying algorithms and algorithmic systems. (3) The Metaphors deck consists of a variety of metaphors that have (or could be) used to describe and discuss algorithms and algorithmic systems. (4) The Caveats deck is full of surprises and unexpected requirements. The cards in this deck are meant to force new lines of thinking!
This box is the product of a Nordic collaboration in the scope of the NOS-HS workshop series Nordic Perspectives on Algorithmic Systems: Concepts, Methods, and Interventions during 2019-2022. Nordic Perspectives on Algorithmic Systems: Concepts, Methods, and Interventions was a series of three workshops, situated in the emerging area of critical algorithm studies. The workshops were geared to develop a Nordic perspective to the social study of algorithms, adding diversity to the academic status quo and improving conceptual frameworks and methods for addressing problems pertaining to the social implications of algorithmic systems. The workshop series was led by Airi Lampinen from Stockholm University, in close collaboration with Marisa Cohn and Pedro Ferreira from IT University of Copenhagen, Asko Lehmuskallio and Thomas Olsson from Tampere University, Matti Nelimarkka from Aalto University and Barry Brown from Stockholm University.
Drawing upon contributions from network members, these cards were originally put together for our meeting in Copenhagen. The game design workshop in Copenhagen was led by Michael Hockenhull and Mace Ojala. The design of the card decks in this box was led by Airi Lampinen, Pedro Ferreira, Matti Nelimarkka, Michael Hockenhull, Jesse Haapoja, Marisa Cohn and Juho Pääkkönen. The visual design of the card box and the cards was done by Rebeca Blanco. The effort to design this card box has also been supported by the Kone Foundation project Algorithmic Systems, Power and Interaction and the Swedish Research Council grant No. 2017-05382_3.
</p
Dismantling Digital Cages: Examining Design Practices for Public Algorithmic Systems
No full textAlgorithmic systems used in public administration can create or reinforce digital cages. A digital cage refers to algorithmic systems or information architectures that create their own reality through formalization, frequently resulting in incorrect automated decisions with severe impact on citizens. Although much research has identified how algorithmic artefacts can contribute to digital cages and their unintended consequences, the emergence of digital cages from human actions and institutions is poorly understood. Embracing a broader lens on how technology, human activity, and institutions shape each other, this paper explores what design practices in public organizations can result in the emergence of digital cages. Using Orlikowski’s structurational model of technology, we found four design practices in observations and interviews conducted at a consortium of public organizations. This study shows that design processes of public algorithmic systems (1) are often narrowly focused on technical artefacts, (2) disregard the normative basis for these systems, (3) depend on involved actors’ awareness of socio-technics in public algorithmic systems, (4) and are approached as linear rather than iterative. These four practices indicate that institutions and human actions in design processes can contribute to the emergence of digital cages, but also that institutional – opposed to technical – possibilities to address their unintended consequences are often ignored. Further research is needed to examine how design processes in public organizations can evolve into socio-technical processes, can become more democratic, and how power asymmetries in the design process can be mitigated.Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.Information and Communication TechnologyEngineering, Systems and Service
On Floridi's method of levels of abstraction
No full textAbstraction is arguably one of the most important methods in modern science in analysing and understanding complex phenomena. In his book The Philosophy of Information, Floridi (The philosophy of information. Oxford University Press, Oxford, 2011) presents the method of levels of abstraction as the main method of the Philosophy of Information. His discussion of abstraction as a method seems inspired by the formal methods and frameworks of computer science, in which abstraction is operationalised extensively in programming languages and design methodologies. Is it really clear what we should understand by levels of abstraction? How should they be specified? We will argue that levels of abstraction should be augmented with annotations, in order to express semantic information for them and reconcile the method of level of abstraction (LoA's) with other approaches. We discuss the extended method when applied e.g. to the analysis of abstract machines. This will lead to an example in which the number of LoA's is unbounded
A note on recursively enumerable classes of partial recursive functions
No full textWe prove that every recursively enumerable class of partial recursive functions with infinite domains must have a recursive witness array. The result gives a powerful method for proving properties of recursively enumerable classes. We show for example that no finitely generated group of recursive permutations can contain all recursive involutions, and neither can it contain all cycle-free recursive permutations
Wireless Sensor Networks: Structure and Algorithms
No full textIn this thesis we look at various problems in wireless networking. First we consider two problems in physical-model networks. We introduce a new model for localisation. The model is based on a range-free model of radio transmissions. The first scheme is randomised and we analyse its expected performance. Then we introduce the concept of a splitline schedule. We conjecture that a certain class of schedules (the regular schedules) is optimal. We prove this for some restricted cases, but the general case remains open. Then we introduce the reverse-binary schedule and prove that it is within a constant factor of optimal. Next we consider the scheduling of wireless transmissions. We give an exact exponential-time algorithm for the Link Independent Set problem. Its branching rules are valid for arbitrary gain matrices, but designed to take advantage of the structure available in geometric instances. We prove a worst-case bound of O*(1.888^n) on the runtime of the algorithm, but only under an assumption on the input. Next we experimentally demonstrate that this assumption is reasonable for random geometric instances and that, in fact, the effective branching factor of the algorithm is expected to be much better than 1.888 on such instances. Finally we show that density is a meaningful structural parameter: experiments as well as theory tell us that the size of the optimal link independent set is closely tied the density of the instance. After these results for physical-model networks, we turn our attention to graphs. We introduce a model of recoverable routing in the presence of node failures. The model is based on the concept of backup nodes: for every node in the network, we assign a backup node that will take over in case the original node fails. These backup nodes are used to fix a route easily and locally. We resolve the basic algorithmic and complexity-related questions about this problem: some variants are polynomial-time solvable and others are NP-complete. For the former we give an O(n^4)-time algorithm. We give non-trivial exponential-time algorithms for the hard cases of the problem. Then we look at a variant of the problem where the basic path is given and we are merely asked to pick which node is backed up by which other node. Again we see that the problem has variants that are polynomial-time solvable and variants that are NP-complete. We give algorithms for all variants. Lastly, we look at a problem of energy-efficient data gathering in wireless sensor networks. We formalise a version of this problem and call it energy-constrained flow. We study, in particular, the integer version of the problem. We prove NP-hardness and hardness of approximation in various settings. Among other results, we show that the problem is strongly NP-complete on geometric configurations on a line. After these mostly-negative results, we present a column generation algorithm for the fractional relaxation of energy-constrained flow. It performs well and we demonstrate experimentally that this approach also leads to an effective heuristic for the integer problem. We finish the thesis with two algorithms with advantage, improving the best known approximation factor when restricted to st-planar networks
Treewidth Computations II. Lower Bounds
No full textAbstractFor several applications, it is important to be able to compute the treewidth of a given graph and to find tree decompositions of small width reasonably fast. Good lower bounds on the treewidth of a graph can, amongst others, help to speed up branch and bound algorithms that compute the treewidth of a graph exactly. A high lower bound for a specific graph instance can tell that a dynamic programming approach for solving a problem is infeasible for this instance. This paper gives an overview of several recent methods that give lower bounds on the treewidth of graphs
Governing Algorithmic Systems in the Social Domain: Providing a socio-technical description of algorithmic systems in the SUWI-domain using Systems Safety and Actor Analyses
No full textThis research looked into Algorithmic Systems used in the execution of the SUWI-law by executing agencies. It analysed the use and governance of these systems and their possible harms to citizens and society by means of an Actor Analysis and System-Theoretical Process Analysis (STPA), supported by semi-structured interviews. It aimed to answer the following research question: How can a systems safety perspective combined with an actor perspective be used to provide a sociotechnical description of algorithmic systems, their governance and possible hazards at agencies executing the SUWI-law?By means of the Actor Analysis, this research was able to describe the actor field and implications of it on the problem situation. The main insight from the actor field was the presence of ‘double binds’, several value conflicts that trouble use of AS. STPA, a method that focusses on safety of a system as a whole rather than individual components, provided the ability to map algorithmic systems within their sociotechnical context. It focussed on three hazards, which are system states that lead to accidents. These three hazards were the use of flawed logic in algorithmic systems, the use of flawed information in algorithmic system, and the flawed understanding citizens have of the role of the systems. They were explored through a Safety Control Structure, which displays controlled processes and those controlling them, and the construction of causal scenarios. Semi-structured interviews focussed on the governance of algorithmic systems, and possible improvements. They provided empirical input for STPA.The main contributions of this research are the proposal it makes for a sociotechnical description of algorithmic systems and their harms, using concepts derived from STPA. Such descriptions can be used to build shared understanding of algorithmic systems and their harms. It showed how such a description can be constructed using an Actor Analysis, interviews, and STPA, describing how these methods work together. Complex Systems Engineering and Management (CoSEM
Pure Nash Equilibria in Graphical Games and Treewidth
Full text linkWe treat PNE-GG, the problem of deciding the existence of a Pure Nash Equilibrium in a graphical game, and the role of treewidth in this problem. PNE-GG is known to be (Formula presented.)-complete in general, but polynomially solvable for graphical games of bounded treewidth. We prove that PNE-GG is (Formula presented.)-Hard when parameterized by treewidth. On the other hand, we give a dynamic programming approach that solves the problem in (Formula presented.) time, where (Formula presented.) is the cardinality of the largest strategy set and (Formula presented.) is the treewidth of the input graph (and (Formula presented.) hides polynomial factors). This proves that PNE-GG is in (Formula presented.) for the combined parameter (Formula presented.). Moreover, we prove that there is no algorithm that solves PNE-GG in (Formula presented.) time for any (Formula presented.), unless the Strong Exponential Time Hypothesis fails. Our lower bounds implicitly assume that (Formula presented.); we show that for (Formula presented.) the problem can be solved in polynomial time. Finally, we discuss the implication for computing pure Nash equilibria in graphical games (PNE-GG) of (Formula presented.) treewidth, the existence of polynomial kernels for PNE-GG parameterized by treewidth, and the construction of a sample and maximum-payoff pure Nash equilibrium
Turing machines with one-sided advice and the acceptance of the co-RE languages
No full textWe resolve an old problem, namely to design a ‘natural’ machine model for accepting the complements of recursively enumerable languages
- …
