The department's research is directed to the foundations of computational models, processes and structures, and the way they support the engineering of software intensive systems. Specific areas of interest are:

Algebraic and Categorical Structures and Methods

Algorithm Design, Analysis and Engineering

Computational Complexity of Algebraic Structures

Deduction, Rewriting and Transformation

Interaction Design and Evaluation of Socio-technical Systems

When downloading papers please observe the normal copyright codes and conventions for their use.

Recent Submissions

Bin packing in multiple dimensions

I mentioned in a previous column [22] that the best known lower bound for the two-dimensional
online bin packing problem is 1.907 by Blitz, van Vliet, Woeginger [2], which is an unpublished
(and now lost [24]) manuscript. I have realized since then that even the penultimate result, 1.856,
was published only in Andre van Vliet's Ph.D. thesis [23] and is not readily available. It therefore
seems like a good idea to describe his methods here, though not in full detail. This will includ...

van Stee, Rob

Online algorithms with advice for bin packing and scheduling problems

We consider the setting of online computation with advice and study the bin packing problem and a number of scheduling problems. We show that it is possible, for any of these problems, to arbitrarily approach a competitive ratio of 1 with only a constant number of bits of advice per request. For the bin packing problem, we give an online algorithm with advice that is (1+ε)-competitive and uses O(1εlog 1ε) bits of advice per request. For scheduling on m identical machines, with the objective f...

Renault, Marc P.; Rosén, Adi; van Stee, Rob

Efficient Embedded Software Migration towards Clusterized Distributed-Memory Architectures

A large portion of existing multithreaded embedded sofware has been programmed according to symmetric shared memory platforms where a monolithic memory block is shared by all cores. Such platforms accommodate popular parallel programming models such as POSIX threads and OpenMP. However with the growing number of cores in modern manycore embedded architectures, they present a bottleneck related to their centralized memory accesses. This paper proposes a solution tailored for an efficient execu...

The cost of selfishness for maximizing the minimum load on uniformly related machines

Consider the following scheduling game. A set of jobs, each controlled by a selfish agent, are to be assigned to m uniformly related machines. The cost of a job is defined as the total load of the machine that its job is assigned to. A job is interested in minimizing its cost, while the social objective is maximizing the minimum load (the value of the cover) over the machines. This goal is different from the regular makespan minimization goal, which was extensively studied in a game theoretic...

Epstein, L.; Kleiman, E.; Van Stee, Rob

SIGACT news online algorithms column 23

van Stee, Rob

Dividing connected chores fairly

In this paper we consider the fair division of chores (tasks that need to be performed by agents, with negative utility for them), and study the loss in social welfare due to fairness. Previous work has been done on this so-called price of fairness, concerning fair division of cakes and chores with non-connected pieces and of cakes with connected pieces. In this paper, we consider situations where each player has to receive one connected piece of the chores. We provide tight or nearly tight b...

Heydrich, S.; van Stee, Rob

Dealing with Multiple Classes in Online Class Imbalance Learning

x

Wang, S.; Minku, Leandro Lei; Yao, X.

SIGACT News Online Algorithms Column 27: Online Matching on the Line, Part 1

Van Stee, Rob

A Unified Approach to Truthful Scheduling on Related Machines

We present a unified framework for designing deterministic monotone polynomial time approximation schemes (PTASs) for a wide class of scheduling problems on uniformly related machines. This class includes (among others) minimizing the makespan, maximizing the minimum load, and minimizing the p-norm of the machine loads vector. Previously, this kind of result was only known for the makespan objective. Monotone algorithms have the property that an increase in the speed of a machine cannot decre...

Van Stee, Rob; Epstein, L.; Levin, A.

A calculus for local reversibility

x

Kuhn, Stefan; Ulidowski, Irek

Run-Time Resolution of Service Property Conflicts in Web Service Composition

With rapid development of Web service technologies, service composition has become a common approach to realizing complex business processes. Due to the large number of services developed and deployed independently by various providers, undesirable interactions between properties of different service components may occur when they are composed into a composite service. Such service property conflicts become a serious obstacle for service composition to meet users' requirements. Although tradi...

Xu, J.; Ning, X.; Reiff-Marganiec, Stephan; Duan, Q.; Zheng, Z.

Extracting Visual Contracts from Java Programs

Visual contracts model the operations of components or services by pre-and post-conditions formalised as graph transformation rules. They provide a precise intuitive notation to support testing, understanding and analysis of software. However, due to their detailed specification of data states and transformations, modelling real applications is an error-prone process. In this paper we propose a dynamic approach to reverse engineering visual contracts from Java based on tracing the execution o...

Heckel, Reiko; Alshanqiti, Abdullah

Which Data Mining Method Do You Need?

Minku, Leandro Lei

The Wisdom of the Crowds in Software Engineering Predictive Modelling

Minku, Leandro Lei

The Best Two-Phase Algorithm for Bin Stretching

Online Bin Stretching is a semi-online variant of bin packing in which the algorithm has to use the same number of bins as an optimal packing, but is allowed to slightly overpack the bins. The goal is to minimize the amount of overpacking, i.e., the maximum size packed into any bin. We give an algorithm for Online Bin Stretching with a stretching factor of $1.5$ for any number of bins. We build on previous algorithms and use a two-phase approach. We also show that this approach cannot give be...

Böhm, M.; Sgall, J.; Van Stee, Rob; Veselý, P.

Finitary Logics for Coalgebras with Branching

The purpose of this dissertation is to further previous work on coalgebras as infinite statebased
transition systems and their logical characterisation with particular focus on infinite
regular behaviour and branching.
Finite trace semantics is well understood [DR95] for nondeterministic labelled transition
systems, and has recently [Jac04, HJS06] been generalised to a coalgebraic level
where monads act as branching types for instance, of nondeterministic choice. Finite
trace semantics ...

Kissig, Christian

FEDD: Feature Extraction for Explicit Concept Drift Detection in Time Series

A time series is a sequence of observations col- lected over fixed sampling intervals. Several real-world dynamic processes can be modeled as a time series, such as stock price movements, exchange rates, temperatures, among others. As a special kind of data stream, a time series may present concept drift, which affects negatively time series analysis and forecasting. Explicit drift detection methods based on monitoring the time series features may provide a better understanding of how concept...

Cavalcante, R.; Minku, Leandro Lei; Oliveira, A.

Dynamic Selection of Evolutionary Operators Based on Online Learning and Fitness Landscape Analysis

Self-adaptive mechanisms for the identification of the most suitable variation operator in evolutionary algorithms rely almost exclusively on the measurement of the fitness of the offspring, which may not be sufficient to assess the optimality of an operator (e.g., in a landscape with an high degree of neutrality). This paper proposes a novel adaptive operator selection mechanism which uses a set of four fitness landscape analysis techniques and an online learning algorithm, dynamic weighted ...

Consoli, P. A.; Mei, Y.; Minku, Leandro Lei; Yao, X.

On Recovering from Run-time Misbehaviour in ADR

We propose a monitoring mechanism for recording the evolution of systems after certain computations, maintaining the history in a tree-like structure. Technically, we develop the monitoring mechanism in a variant of ADR (after Architectural Design Rewriting), a rule-based formal framework for modelling the evolution of architectures of systems. The hierarchical nature of ADR allows us to take full advantage of the tree-like structure of the monitoring mechanism. We exploit this mechanism to f...