Cologne Excellence Cluster on Cellular Stress Responses in Aging Associated Diseases
computer science publication serverNot a member yet
819 research outputs found
Sort by
Probabilistic Analysis of Random Mixed Horn Formulas
No full textWe present a probabilistic analysis of random mixed Horn formulas (MHF), i.e., formulas in conjunctive normal form consisting of a positive monotone part of quadratic clauses and a part of Horn clauses, with m clauses, n variables, and up to n literals per Horn clause. For MHFs parameterized by n and m with uniform distribution of instances and for large n, we derive upper bounds for the expected number of models. For the class of random negative MHFs, where only monotone negative Horn clauses are allowed to occur, we give a lower bound for the probability that formulas from this class are satisfiable. We expect that the model studied theoretically here may be of interest for the determination of hard instances, which are conjectured to be found in the transition area from satisfiability to unsatisfiability of the instances from the parameterized classes of formulas
On weighted efficient total domination
No full textAn efficiently total dominating set of a graph G is a subset of its vertices, such that every vertex of G is adjacent to exactly one vertex of the subset. If there is such a subset, then G is an efficiently total dominatable graph (G is etd). We present two graph classes on which the weighted etd problem is polynomially solvable: claw-free graphs and graphs which only induce cycles of length divisible by four. Furthermore, claw-free etd graphs are shown to be perfect
A Satisfiability-based Approach for Generalized Tanglegrams on Level Graphs
No full textA tanglegram is a pair of (not necessarily binary) trees on the same set of leaves with matching leaves in the two trees joined by an edge. Tanglegrams are widely used in computational biology to compare evolutionary histories of species. In this work we present a formulation of two related combinatorial embedding problems concerning tanglegrams in terms of CNF-formulas. The first problem is known as the planar embedding and the second as the crossing minimization problem. We show that our satisfiability-based encoding of these problems can handle a much more general case with more than two, not necessarily binary or complete, trees defined on arbitrary sets of leaves and allowed to vary their layouts. Furthermore, we present an experimental comparison of our technique and several known heuristics for solving generalized binary tanglegrams, showing its competitive performance and efficiency and thus proving its practical usability
Sentiment classification using statistical data compression models
No full textWith growing availability and popularity of user
generated content, the discipline of sentiment analysis
has come to the attention of many researchers. Existing
work has mainly focused on either knowledge based
methods or standard machine learning techniques. In
this paper we investigate sentiment polarity classification
based on adaptive statistical data compression models. We evaluate the classification performance of the lossless compression algorithm Prediction by Partial Matching (PPM) as well as compression based measures using PPM-like character n-gram frequency statistics. Comprehensive experiments on three corpora show that compression based methods are efficient, easy to apply and can compete with the accuracy of sophisticated classifiers such as support vector machines
Models and Algorithms for Robust Network Design with Several Traffic Scenarios
No full textWe consider a robust network design problem in which optimum
integral capacities need to be installed on the edges of a network
such that the supplies and demands in each of the explicitly known traffic scenarios are satisfied by a single-commodity flow. In Buchheim et al.
(LNCS 6701, 7 - 17 (2011)), an integer-programming (IP) formulation
of polynomial size was given that uses both
flow and capacity variables.
In this work, we introduce an IP formulation that only uses capacity
variables and exponentially many constraints that can be separated in
polynomial time. We argue that the latter formulation has advantageous
features when used within branch and cut and evaluate preliminary computational
results for the bounds in the root node. We introduce a class
of instances that is difficult for IP-based solution approaches. We design
and implement a heuristic solution approach based on the definition and
exploration of large neighborhoods of carefully selected size. The performance
of the heuristic is evaluated on the difficult class of instances.
The results are encouraging, with a good understanding of the trade-off
between solution quality and neighborhood size
Simulation and optimization of Cologne's tram schedule
No full textIn many tram networks multiple lines share tracks and stations, thus requiring robust schedules which prevent inevitable delays from spreading through the network. Feasible schedules also have to fulfill various planning requirements originating from political and economical reasons.
In this paper we present a tool set designed to generate schedules optimized for robustness, which also satisfy given sets of planning requirements. These tools allow us to compare time tables with respect to their applicability and evaluate them prior to their implementation in the field.
This paper begins with a description of the tool set focusing on optimization and simulation modules. These software utilities are then employed to generate schedules for our hometown Cologne's tram network, and to subsequently compare them for their applicability
Modeling time table based tram traffic
No full textIn mid-sized cities, tram networks are major components of public service infrastructure. In those networks with their typically dense schedules, multiple lines share tracks and stations, resulting in a dynamic system behavior and mounting delays following even small disruptions. Robustness is an important factor to keep delays from spreading through the network and to minimize average delays.
This paper describes part of a project on simulation and optimization of tram schedules, namely the devel-opment and application of a simulation model representing a tram network and its assigned time table. We begin by describing the components of a tram network, which consist of physical and logical entities. These concepts are then integrated into a model of time table based tram traffic. We apply the resulting simulation software to our hometown Cologne's tram network and present some experimental results
