1,721,066 research outputs found
The complexity and expressive power of valued constraints
Full text linkThis thesis is a detailed examination of the expressive power of valued constraints and related complexity questions. The valued constraint satisfaction problem (VCSP) is a generalisation of the constraint satisfaction problem which allows to describe a variety of combinatorial optimisation problems. Although most results are stated in this framework, they can be interpreted equivalently in the framework of, for instance, pseudo-Boolean polynomials, Gibbs energy minimisation, or Markov Random Fields. We take a result of Cohen, Cooper and Jeavons that characterises the expressive power of valued constraint in terms of certain algebraic properties, and extend this result by showing yet another connection between the expressive power of valued constraints and linear programming. We prove a decidability result for fractional clones. We consider various classes of valued constraints and the associated cost functions with respect to the question of which of these classes can be expressed using only cost functions of bounded arities. We identify the first known example of an infinite chain of classes of constraints with strictly increasing expressive power. We present a full classification of various classes of constraints with respect to this problem. We study submodular constraints and cost functions. Submodular functions play a key role in combinatorial optimisation and are often considered to be a discrete analogue of convex functions. It has previously been an open problem whether all Boolean submodular cost functions can be decomposed into a sum of binary submodular cost functions over a possibly larger set of variables. This problem has been considered within several different contexts in computer science, including computer vision, artificial intelligence, and pseudo-Boolean optimisation. Using a connection between the expressive power of valued constraints and certain algebraic properties of cost functions, we answer this question negatively. Our results have several corollaries. First, we characterise precisely which submodular polynomials of degree 4 can be expressed by quadratic submodular polynomials. Next, we identify a novel class of submodular functions of arbitrary arities that can be expressed by binary submodular functions, and therefore minimised efficiently using a so-called expressibility reduction to the (s,t)-Min-Cut problem. More importantly, our results imply limitations on this kind of reduction and establish for the first time that it cannot be used in general to minimise arbitrary submodular functions. Finally, we refute a conjecture of Promislow and Young on the structure of the extreme rays of the cone of Boolean submodular functions
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Cellular distributed and parallel computing
Full text linkThis thesis focuses on novel approaches to distributed and parallel computing that are inspired by the mechanism and functioning of biological cells. We refer to this concept as cellular distributed and parallel computing which focuses on three important principles: simplicity, parallelism, and locality. We first give a parallel polynomial-time solution to the constraint satisfaction problem (CSP) based on a theoretical model of cellular distributed and parallel computing, which is known as neural-like P systems (or neural-like membrane systems). We then design a class of simple neural-like P systems to solve the fundamental maximal independent set (MIS) selection problem efficiently in a distributed way, by drawing inspiration from the way that developing cells in the fruit fly become specialised. Building on the novel bio-inspired approach to distributed MIS selection, we propose a new simple randomised algorithm for another fundamental distributed computing problem: the distributed greedy colouring (GC) problem. We then propose an improved distributed MIS selection algorithm that incorporates for the first time another important feature of the biological system: adapting the probabilities used at each node based on local feedback from neighbouring nodes. The improved distributed MIS selection algorithm is again extended to solve the distributed greedy colouring problem. Both improved algorithms are simple and robust and work under very restrictive conditions, moreover, they both achieve state-of-the-art performance in terms of their worst-case time complexity and message complexity. Given any n-node graph with maximum degree Delta, the expected time complexity of our improved distributed MIS selection algorithm is O(log n) and the message complexity per node is O(1). The expected time complexity of our improved distributed greedy colouring algorithm is O(Delta + log n) and the message complexity per node is again O(1). Finally, we provide some experimental results to illustrate the time and message complexity of our proposed algorithms in practice. In particular, we show experimentally that the number of colours used by our distributed greedy colouring algorithms turns out to be optimal or near-optimal for many standard graph colouring benchmarks, so they provide effective simple heuristic approaches to computing a colouring with a small number of colours
Algorithmic biology of evolution and ecology
Full text linkAny process can be seen as an algorithm; its power and its limits can then be analysed with the techniques of theoretical computer science. To analyse algorithms, we divide the world in two: the problem space that shapes what might happen and the dynamics of what does happen. If we fix an idealised framework for one of the two, then we can obtain powerful general results by abstracting over the other. This “algorithmic lens” can be used to view both artificial and natural processes, including the natural processes of biological evolution.
In Part I, I idealize the space of evolution as a fitness landscape so that I can abstract over the possible evolutionary dynamics. I show that fitness landscapes can be represented by gene-interaction networks that encode the structure of epistasis.
For some landscapes, the epistatic structure produces a computational constraint that prevents evolution from finding even a local fitness optimum—thus contradicting the traditional assumption that local fitness peaks can always be reached quickly by natural selection. I introduce a distinction between easy landscapes, where local fitness peaks can be found in a moderate number of steps, and hard landscapes where finding any such local optimum requires an infeasible amount of time. Hard examples exist where strong-selection weak-mutation dynamics cannot find a local peak in polynomial time, even when it is known to be unique. More generally, I show that hard fitness landscapes exist where no evolutionary dynamics—even ones that do not follow adaptive paths—can find a local fitness optimum in polynomial time. Moreover, on hard landscapes, the fitness advantage of nearby mutants cannot drop off exponentially fast but must follow a power-law, similar to the one found by long-term evolution experiments, associated with unbounded growth in fitness. Thus, the constraint of computational complexity enables open-ended evolution on finite landscapes. I present candidates for hard landscapes at scales from single genes, to microbes, to complex organisms with costly learning (Baldwin effect) or maintained cooperation (Hankshaw effect). Finally, by looking closer at the fine structure of epistasis, I also extend the class of provably easy landscapes to include all those with tree-structured gene-interaction networks.
In Part II, I idealize the dynamics of evolution as replicator dynamics so that I can abstract over the space of ecologies (interactions between organisms). This requires replacing the fitness-as-scalar concept used in fitness landscapes by a fitness-as-function concept derived from evolutionary game theory. Since they have not been adequately defined or interpreted in the context of microscopic biology, I provide two interpretations of the central objects of game theory: one that leads to what I call “reductive games” and the other to “effective games”. These interpretations are based on the difference between views of fitness as a property of tokens versus fitness as a summary statistic of types. Reductive games are typical of theoretical work like agent-based models. Effective games correspond more closely to experimental work and allow for empirical abstraction over poorly characterized interaction mechanisms like spatial structure.
This empirical abstraction allows me to analyse the in vitro evolution of resistance to cancer therapy. I develop a game assay to directly measure effective evolutionary games in co-cultures of non-small cell lung cancer cells that are sensitive vs resistant to the targeted drug Alectinib. I show that the games are not only quantitatively different between different environments, but that the presence of the drug or the absence of cancer-associated fibroblasts qualitatively switches the type of game being played by the in vitro population. This observation provides empirical confirmation of a central theoretical postulate of evolutionary game theory in oncology: we can treat not only the player, but also the game.
Thus through the whole thesis, I demonstrate how the algorithmic lens and abstraction can help us derive new ways of seeing and understanding both evolution and ecology
Hybrid tractability of constraint satisfaction problems with global constraints
Full text linkA wide range of problems can be modelled as constraint satisfaction problems (CSPs), that is, a set of constraints that must be satisfied simultaneously. Constraints can either be represented extensionally, by explicitly listing allowed combinations of values, or intensionally, whether by an equation, propositional logic formula, or other means. Intensionally represented constraints, known as global constraints, are a powerful modelling technique, and many modern CSP solvers provide them. We give examples to show how problems that deal with product configuration can be modelled with such constraints, and how this approach relates to other modelling formalisms.The complexity of CSPs with extensionally represented constraints is well understood, and there are several known techniques that can be used to identify tractable classes of such problems. For CSPs with global constraints, however, many of these techniques fail, and far fewer tractable classes are known. In order to remedy this state of affairs, we undertake a systematic review of research into the tractability of CSPs. In particular, we look at CSPs with extensionally represented constraints in order to understand why many of the techniques that give tractable classes for this case fail for CSPs with global constraints. The above investigation leads to two discoveries.First, many restrictions on how the constraints of a CSP interact implicitly rely on a property of extensionally represented constraints to guarantee tractability. We identify this property as being a bound on the number of solutions in key parts of the instance, and find classes of global constraints that also possess this property. For such classes, we show that many known tractability results apply. Furthermore, global constraints allow us to treat entire CSP instances as constraints. We combine this observation with the above result, and obtain new tractable classes of CSPs by dividing a CSP into smaller CSPs drawn from known tractable classes. Second, for CSPs that simply do not possess the above property, we look at how the constraints of an instance overlap, and how assignments to the overlapping parts extend to the rest of the problem. We show that assignments that extend in the same way can be identified. Combined with a new structural restriction, this observation leads to a second set of tractable classes.We conclude with a summary, as well as some observations about potential for future work in this area
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
On the bridge between constraint satisfaction and Boolean satisfiability
Full text linkA wide range of problems can be formalized as a set of constraints that need to be satisfied. In fact, such a model is called a constraint satisfaction problem (CSP). Another way to represent a problem is to express it as a formula in propositional logic, or, in other words, a Boolean satisfiability problem (SAT). In the quest to find efficient algorithms for solving instances of CSP and SAT specialised software has been developed. It is, however, not clear when should we choose a SAT-solver over a constraint solver (and vice versa). CSP-solvers are known for their domain-specific reasoning, whereas SAT-solvers are considered to be remarkably fast on Boolean instances. In this thesis we tackle these issues by investigating the connections between CSP and SAT.In order to answer the question why SAT-solvers are so efficient on certain classes of CSP instances, we first present the various ways one can encode a CSP instance into SAT. Next, we show that with some encodings SAT-solvers simulate the effects of enforcing a form of local consistency, called k-consistency, in expected polynomial-time. Thus SAT-solvers are able to solve CSP instances of bounded-width structure efficiently in contrast to conventional constraint solvers. By considering the various ways one can encode CSP domains into SAT, we give theoretical reasons for choosing a particular SAT encoding for several important classes of CSP instances. In particular, we show that with this encoding many problem instances that can be solved in polynomial-time will still be easily solvable once they are translated into SAT. Furthermore, we show that this is not true for several other encodings.Finally, we compare the various ways one can use a SAT-solver to solve the classical problem of the pigeonhole principle. We perform both theoretical and empirical comparison of the various encodings. We conclude that none of the known encodings for the classical representation of the problem will result in an efficiently-solvable SAT instance. Thus in this case constraint solvers are a much better choice
- …
