We explore the performance of the recently proposed two-view image matching algorithms using affine view synthesis -- ASIFT (Morel and Yu, 2009) and MODS (Mishkin, Perdoch and Matas, 2013) on images of objects that do not have significant local texture and that are locally not well approximated by planes.

Experiments show that view synthesis improves matching results on images of such objects, but the number of "useful" synthetic views is lower than for planar objects matching. The best detector for matching images of 3D objects is the Hessian-Affine in the Sparse configuration. The iterative MODS matcher performs comparably confirming it is a robust, generic method for two view matching that performs well for different types of scenes and a wide range of viewing conditions.

Recent modeling experiments conducted in computational music give evidence that number of concepts, methods and tools belonging to inverse semigroup theory can be attuned towards the concrete modeling of time-sensitive interactive systems. Further theoretical developments show that some related notion of higher-dimensional strings can be used as a unifying theme across word or tree automata theory. In this lecture, we will provide a guided tour of this emerging theory, both as an abstract theory and with a view to concrete applications.

The paper presents an update of the change of expectations and most recent new approaches regarding software processes and their improvement following the Software Process Improvement Hype Cycle introduced earlier by the author as an extension of the Gartner Hype Cycle idea. Software process assessment and improvement can itself be considered on the more abstract level as a quest for compliance with best practices. Etics and regulatory regimes explicitly addressing safety- critical systems mean however stringent compliance requirements beyond the commitment to improve process capability. New approaches are nec- essary for software engineers to fulll the considerably growing expecta- tions regarding quality under much slower changing development bud- get and deadline constraints. Open Services for Lifecycle Collaboration (OSLC) is the emerging initiative inspired by the web which is currently at the technology trigger stage along its hype cycle with the potential to have a determining impact on the future of Software Process Compliance Engineering.

In this talk I will discuss two types of models used to define the security of cryptographic systems. One originates in work on formal languages and logics, the other is based on probability theory and computational complexity. I will explain that the two approaches have complementary strengths and weaknesses and that it is sometimes possible to obtain the best of both worlds. If time permits I will go over two examples, one related to protocol verification and the other from the area of cryptographically enforced access control.

We impose various oracle mechanisms on nondeterministic pushdown automata, which naturally induce nondeterministic reducibilities among formal languages in a theory of context-free languages. In particular, we examine a notion of nondeterministic many-one CFL-reducibility and conduct a ground work to formulate a coherent framework for further expositions. Two more powerful reducibilities--bounded truth-table and Turing CFL-reducibilities--are also discussed in comparison. The Turing CFL-reducibility, in particular, makes it possible to induce a useful hierarchy (the CFL hierarchy) built over the family CFL of context-free languages. For each level of this hierarchy, basic structural properties are proven and three alternative characterizations are presented. The first and second levels of the hierarchy are proven to be different. The rest of the hierarchy is also infinite unless the polynomial hierarchy over NP collapses. This follows from a characterization of the Boolean hierarchy over the k-th level of the polynomial hierarchy in terms of the Boolean hierarchy over the (k+1)st level of the CFL hierarchy. We argue that the CFL hierarchy coincides with a hierarchy over CFL built by applications of many-one CFL-reductions.

This paper presents an extension to the Service Oriented Development Method (SOD-M) to support the representation of some non-functional requirements. Specifically, we propose to extend SOD-M with:

• meta-models for representing non-functional requirements in different abstraction levels;
• model to model transformation rules, useful to semi-automatically refine Platform Independent Models into Platform Specific Models; and
• rules to transform Platform Specific Models into concrete implementations.

We apply our proposal to develop a proof-of-concept example.

We consider unary finite automata employing limited nondeterminism. We show that for a unary regular language, a minimal finite tree width nondeterministic finite automaton (NFA) can always be found in Chrobak normal form. A similar property holds with respect to other measures of nondeterminism. The latter observation is used to establish relationships between classes of unary regular languages recognized by NFAs of given size where the nondeterminism is limited in various ways. Finally, we show that the branching measure of a unary NFA is always either bounded by a constant or has an exponential growth rate.

Contemporary enterprise web applications must deal with a large stack of different kinds of concerns involving business rules, security policies, cross-cutting configuration, etc. At the same time, increasing demands on user interface complexity make designers to consider the above concerns in the presentation. To locate a concern knowledge, we try to identify an appropriate system component with the concern definition. Unfortunately, this is not always possible, since there exist concerns cross-cutting multiple components. Thus to capture the entire knowledge we need to locate multiple components. In addition to it, often, we must restated the knowledge in the user interface because of technological incompatibility between the knowledge source and the user interface language. Such design suffers from tangled and hard to read code, due to the cross-cutting concerns and also from restated information and duplicated knowledge. This leads to a product that is hard to maintain, a small change becomes expensive, error-prone and tedious due to the necessity of manual changes in multiple locations.

This paper introduces a novel approach based on independent, description of all orthogonal concerns in information systems and their dynamic automated weaving according to the current user's context. Such approach avoids information restatement, speeds up development and simplifies maintenance efforts due to application of automated programming and runtime weaving of all concerns, and thus distributes the knowledge through the entire system.

De Alfaro and Henzinger introduced interface automata to model and study behavioural types. These come with alternating simulation as refinement and with a specific parallel composition: if one component receives an unexpected input, this is regarded as an error and the resp. error states are removed with a special pruning operation. In this paper, we return to the foundations of interface automata and study how refinement and parallel composition should be defined best. We take as basic requirement that an implementation must be error-free, if the specification is. For three variants of error-free, we consider the coarsest precongruence for parallel composition respecting the basic requirement. We find that pruning proves to be relevant in all cases; we also point out an error in an early paper by de Alfaro and Henzinger.

To cope with the complexity of large systems, one usually makes use of hierarchical structures in their models. To detect and to remove design errors as soon as possible, these models must be analyzed in early stages of the development process. For example, UML models can be analyzed through simulation using the semantics of a foundational subset for executable UML models (fUML). However, the composite structures used to describe the hierarchy of systems in UML is not covered by fUML. In this paper, we therefore propose a complementary meta-model for fUML covering parts of UML's composite structures, and elaborate the rules previously defined in the literature for static semantics. These rules are described in an axiomatic way using first-order logic so that a large set of tools can be used for analysis. Our preliminary evaluation provides results about the applicability of the meta-model and the soundness of the rules.

We investigate the parameterized prefix distance between regular languages. The prefix distance between words is extended to languages in such a way that the distances of all words up to length $n$ to the mutual other language are summed up. Tight upper bounds for the distance between unary as well as non-unary regular languages are derived. It is shown that there are pairs of languages having a constant, degree $k$ polynomial, and exponential distance. Moreover, for every constant and every polynomial, languages over a binary alphabet are constructed that have exactly that distance. From the density and census functions of regular languages the orders of possible distances between languages are derived and are shown to be decidable.

A central problem in the delivery of intensity-modulated radiation therapy (IMRT) using a multileaf collimator (MLC) relies on finding a series of leaves configurations that can be shaped with the MLC to properly deliver a given treatment. In this paper, we analyse, from an algorithmic point of view, the power of using dual-layer MLCs and Rotating Collimators for this purpose.

We propose a stronger conjecture regarding the number of distinct squares in a binary word. Fraenkel and Simpson conjectured in 1998 that the number of distinct squares in a word is upper bounded by the length of the word. Here, we conjecture that in the case of a word of length $n$ over the alphabet $\{a,b\}$, the number of distinct squares is upper bounded by $\frac{2k-1}{2k+2}n$, where $k$ is the least of the number of $a$'s and the number of $b$'s. We support the conjecture by %a series of results showing its validity for several classes of binary words. We also prove that the bound is tight.

We study active learning of recursive functions by asking queries of the type ``$f(17)=\;$?''. The complexity measure in this paper is the worst-case number of queries asked. We prove that for some classes of recursive functions \emph{ultrametric active learning} algorithms can achieve the learning goal by asking \emph{significantly fewer} queries than deterministic, probabilistic, and even nondeterministic active learning algorithms. This is the first ever example of a problem, where ultrametric algorithms have advantages over nondeterministic algorithms.

We introduce a two-dimensional variant of the restarting automaton with window size three-by-three for processing rectangular pictures. In each rewrite step such an automaton can only replace the symbol in the middle position of its window by a symbol that is smaller with respect to a fixed ordering on the tape alphabet. When restricted to one-dimensional inputs (that is, words), the deterministic variant of these `ordered restarting automata' only accepts regular languages, while the nondeterministic one can accept some languages that are not even context-free. We then concentrate on the deterministic two-dimensional ordered restarting automaton, showing that it is quite expressive as it can simulate the deterministic sgraffito automaton, and we present some closure and non-closure properties for the class of picture languages accepted by these automata.

We consider the task of transmitting a data stream in the sliding window model, where communication takes place over an adversarial noisy channel with noise rate up to 1. For any noise level c < 1, we design an efficient (polylogarithmic time) encoding scheme with constant overhead, such that for any window in which the noise level does not exceed c, the receiving end decodes at least a (1-c-\eps)-prefix of the window, for any small \eps > 0. Decoding more than a (1-c)-prefix of the window is shown to be impossible in the worst case, which makes our scheme optimal in this sense.

Graph and cartographic visualization have the common objective to provide intuitive understanding of some underlying data. We consider a problem that combines aspects of both by studying the problem of fitting planar graphs on planar maps. After providing an NP-hardness result for the general decision problem, we identify sufficient conditions so that a fit is possible on a map with rectangular regions. We generalize our techniques to non-convex rectilinear polygons, where we also address the problem of effective distribution of the vertices inside the map regions.

In this contribution, we describe and compare two genetic systems which create trading strategies. The first system is based on the idea that the connection weight matrix of a neural network represents the genotype of an individual and can be changed by genetic algorithm. The second system uses genetic programming to derive trading strategies. As input data in our experiments, we used technical indicators of NASDAQ stocks. As output, the algorithms generate trading strategies, i.e. buy, hold, and sell signals. Our hypothesis that strategies obtained by genetic programming bring better results than buy-and-hold strategy has been proven as statistically significant. We discuss our results and compare them to our previous experiments with fuzzy technology, fractal approach, and with simple technical indicator strategy.

The clique-chromatic number of a graph $G=(V,E)$ denoted by $\chi_c(G)$ is the smallest integer $k$ such that there exists a partition of the vertex set of $G$ into $k$ subsets with the property that no maximal clique of $G$ is contained in any of the subsets. Such a partition is called a $k$-clique-colouring of $G$. Recently Marx proved that deciding whether a graph admits a $k$-clique-colouring is $\Sigma^p_2$-complete for every fixed $k \geq 2$. Our main results are an $O^*(2^n)$ time inclusion-exclusion algorithm to compute $\chi_c(G)$ exactly, and a branching algorithm to decide whether a graph of bounded clique-size admits a $2$-clique-colouring which runs in time $O^*(\lambda^n)$ for some $\lambda < 2$.

As the use of intelligent agents in critical domains increases, the need for verifying heir behavior becomes stronger. Reactive rules are the main reasoning formalism for intelligent agents. For this reason, we propose the use of the OTS/CafeOBJ method for the specification of reactive rules, which will permit the verification of safety properties for reactive rule-based intelligent agents.

The well-known Disjoint Paths problem takes as input a graph G and a set of k pairs of terminals in G, and the task is to decide whether there exists a collection of k pairwise vertex-disjoint paths in G such that the vertices in each terminal pair are connected to each other by one of the paths. This problem is known to NP-complete, even when restricted to planar graphs or interval graphs. Moreover, although the problem is fixed-parameter tractable when parameterized by k due to a celebrated result by Robertson and Seymour, it is known not to admit a polynomial kernel unless NP is a subset of coNP/poly. We prove that Disjoint Paths remains NP-complete on split graphs, and show that the problem admits a kernel with O(k^2) vertices when restricted to this graph class. We furthermore prove that, on split graphs, the edge-disjoint variant of the problem is also NP-complete and admits a kernel with O(k^3) vertices. To the best of our knowledge, our kernelization results are the first non-trivial kernelization results for these problems on graph classes.

In this paper, we focus on small or medium-sized e-commerce portals. Due to high competition, users of these portals are not too loyal and e.g. refuse to register or provide any/enough explicit feedback. Furthermore, products such as tours, cars or furniture have very low average consumption rate preventing us from tracking unregistered user between two consecutive purchases. Recommending on such domains proves to be very challenging, yet interesting research task. For this task, we propose a model coupling various implicit feedbacks and object attributes in matrix factorization. We report on promising results of our initial off-line experiments on travel agency dataset. Our experiments corroborate benefits of using object attributes; however we are yet to decide about usefulness of some implicit feedback data.

Clustering graphs based on a comparison of the number of links within clusters and the expected value of this quantity in a random graph has gained a lot of attention and popularity in the last decade. Recently, Aldecoa and Marín proposed a related, but slightly different approach leading to the quality measure surprise, and reported good behavior in the context of synthetic and real world benchmarks. We show that the problem of finding a clustering with optimum surprise is NP-hard. Moreover, a bicriterial view on the problem permits to compute optimum solutions for small instances by solving a small number of integer linear programs, and leads to a polynomial time algorithm on trees.

Given two sets of strings, similarity joins attempt to find all similar pairs of strings from each respective set. Similarity is estimated by a given similarity function on strings. In this study, we focus on similarity joins with respect to edit distance. Existing approaches have mainly improved their speed performance by filtering algorithms for edit distance calculations, which incur high costs. Further, existing approaches incur large costs also associated with filtering. Therefore, in this paper, we propose bit-based filtering with empirical high speed. This filter, based on a relation between the edit distance and L_1 distance on strings, achieves a reduced candidate size. This filter is rapidly computed by bitwise operations. We demonstrate the effectiveness of this proposed filter through experiments.

The value 1 problem is a natural decision problem in algorithmic game theory. For partially observable Markov decision processes with reachability objective, this problem is defined as follows: are there observational strategies that achieve the reachability objective with probability arbitrarily close to 1? This problem was shown undecidable recently. Our contribution is to introduce a class of partially observable Markov decision processes, namely #-acyclic partially observable Markov decision processes, for which the value 1 problem is decidable. Our algorithm is based on the construction of a two-player perfect information game, called the knowledge game, abstracting the behaviour of a #-acyclic partially observable Markov decision process M such that the first player has a winning strategy in the knowledge game if and only if the value of M is 1.

One of the most representative and studied Distance Based Queries in Spatial Databases is the K Closest Pairs Query (KCPQ). This query involves two spatial data sets and a distance function to measure the degree of closeness, along with a given number K of elements of the result. The output is a set of pairs of objects (with one object element from each set), with the K lowest distances. In this paper, we study the problem of processing KCPQs between RAM-based point sets, using Plane-Sweep (PS) algorithms. We utilize two improvements that can be applied to a PS algorithm and propose a new algorithm that minimizes the number of distance computations, in comparison to the classic PS algorithm. By extensive experimentation, using real and synthetic data sets, we highlight the most efficient improvement and show that the new PS algorithm outperforms the classic one, in most cases.

In activation network problems we are given a directed or undirected graph G=(V,E) with a family { f_{uv}(x_u,x_v): (u,v) in E } of monotone non-decreasing activation functions from D^2 to {0,1}, where D is a constant-size domain, and the goal is to find activation values x_v for all v in V of minimum total cost \sum_{v in V} x_v such that the activated set of edges satisfies some connectivity requirements. We propose algorithms that optimally solve the minimum activation cost $k$ node-disjoint $st$-paths (st-MANDP) problem in O(tw {((5+tw)|D|)}^{2tw+2}|V|^5) time and the minimum activation cost node-disjoint paths (MANDP) problem for k terminal pairs (s_1,t_1),...,(s_k,t_k) in O(tw ((4+3tw)|D|)^{2tw+2}|V|) time for graphs with tree-width bounded by tw.

It is increasingly difficult for customers to understand complex systems like clouds and to trust them with regard to security. As a result, numerous companies achieved a security certification according to the ISO 27001 standard. However, assembling an Information Security Management System (ISMS) according to the ISO 27001 standard is difficult, because the standard provides only sparse support for system development and documentation. Security requirements engineering methods have been used to elicit and analyse security requirements for building software. In this paper, we propose a goal- based security requirements engineering method for creating an ISMS compliant to ISO 27001. We illustrate our method via a smart grid example.

Let ${\cal B}$ be a finite collection of geometric (not necessarily convex) bodies in the plane. Clearly, this class of geometric objects naturally generalizes the class of disks, lines, ellipsoids, and even convex polygons. We consider geometric intersection graphs $G_{\cal B}$ where each body of the collection ${\cal B}$ is represented by a vertex, and two vertices of $G_{\cal B}$ are adjacent if the intersection of the corresponding bodies is non-empty. For such graph classes and under natural restrictions on their maximum degree or subgraph exclusion, we prove that the relation between their treewidth and the maximum size of a grid minor is linear. These combinatorial results vastly extend the applicability of all the meta-algorithmic results of the bidimensionality theory to geometrically defined graph classes.

As the technology grows rapidly and the new applications and systems are being developed every day, it is crucial to have proper protection. Identifying, defining and implementing of security constraints is a very important part of the process of modeling and developing of an application or information systems and its later administration.

The paper presents the issue of security constraints of information system from the point of view of Usage Role-based Access Control approach - it deals with the classification of constraints and their implementation in the process of modeling the access rules for dynamic information systems.

In this paper we study the Sparsest k-Subgraph problem which consists in finding a subset of k vertices in a graph which induces the minimum number of edges. The Sparsest k-Subgraph problem is a natural generalization of the Independent Set problem, and thus is NP-hard (and even W[1]-hard) in general graphs. In this paper we investigate the parameterized complexity of both Sparsest k-Subgraph and Densest k- Subgraph in chordal graphs. We first provide simple proofs that Densest k-Subgraph in chordal graphs is FPT and does not admit a polynomial kernel unless N P ⊆ coN P/poly (both parameterized by k). More involved proofs will ensure the same behavior for Sparsest k-Subgraph in the same graph class.

A variety of system design and architecture description lan- guages, such as SysML, UML or AADL, allows the decomposition of complex system designs into communicating timed components. In this paper we consider the contract-based specification of such components. A contract is a pair formed of an assumption, which is an abstraction of the component’s environment, and a guarantee, which is an abstraction of the component’s behaviour given that the environment behaves accord- ing to the assumption. Thus, a contract concentrates on a specific aspect of the component’s functionality and on a subset of its interface, which makes it relatively simpler to specify. Contracts may be used as an aid for hierarchical decomposition during design or for verification of properties of composites. This paper defines contracts for components formalized as a variant of timed input/output automata, introduces compositional results allowing to reason with contracts and shows how contracts can be used in a high-level modeling language (SysML) for specification and verification, based on an example extracted from a real-life system.

In the disjoint path allocation problem, we consider a path of L+1 vertices, representing the nodes in a communication network. Requests for an unbounded-time communication between pairs of vertices arrive in an online fashion and a central authority has to decide which of these calls to admit. The constraint is that each edge in the path can serve only one call and the goal is to admit as many calls as possible.

Advice complexity is a recently introduced method for a fine-grained analysis of the hardness of online problems. We consider the advice complexity of disjoint path allocation, measured in the length L of the path. We show that asking for a bit of advice for every edge is necessary to be optimal and give online algorithms with advice achieving a constant competitive ratio using much less advice. Furthermore, we consider the case of using less than $\log\log L$ advice bits, where we prove almost matching lower and upper bounds on the competitive ratio.

In the latter case, we moreover show that randomness is as powerful as advice by designing a barely random online algorithm achieving almost the same competitive ratio.

Online Social Networks (OSNs) enjoy high popularity, but their centralized architectures lead to intransparency and mistrust in the providers who can be the single point of failure. A solution is to adapt the OSN functionality to an underlying and fully distributed peer-to-peer (P2P) substrate. Several approaches in the field of OSNs based on P2P architectures have been proposed, but they share substantial P2P weaknesses and they suffer from low availability and privacy problems. In this work, we propose a distributed OSN which combines an underlying P2P architecture with friend-based data propagation and a Proof-of-Work (PoW) concept. ProofBook provides availability of user data, stability of the underlying network architecture and privacy improvements while it does not limit simple data sharing based on social relations.

In this work, we study the advice complexity of the online minimum Steiner tree problem (ST). Given a (known) graph $G = (V, E)$ endowed with a weight function on the edges, a set of $N$ terminals are revealed in a step-wise manner. The algorithm maintains a sub-graph of chosen edges, and at each stage, chooses more edges from $G$ to its solution such that the terminals revealed so far are connected in it. In the standard online setting this problem was studied and a tight bound of $O(log(N))$ on its competitive ratio is known. Here, we study the power of non-uniform advice and fully characterize it. As a first result we show that using $q•log(|V|)$ advice bits, where $0 ≤ q ≤ N −1$ it is possible to obtain an algorithm with a competitive ratio of $O(log(N/q)$. We then show a matching lower bound for all values of $q$, and thus settle the question.

Anonymous authentication protocols aim to provide means to anonymously prove membership in a group. Moreover, the membership should not be transferable i.e. a subgroup of members should not be able to help an outsider to gain access on behalf of a group. In this note we present two attacks on a recently published protocol of this kind (ICUIMC í11 Proceedings of the 5th International Conference on Ubiquitous Information Management and Communication, article no. 32) and thereby we show that it failed the security targets for a anonymous authentication protocol.

This paper concerns probabilistic distributed graph algorithms to solve classical graph problems such as colouring, maximal matching or maximal independent set. We consider anonymous networks (no unique identifiers are available) where vertices communicate by single bit messages. We present a general framework, based on coverings, for proving lower bounds for the bit complexity and thus the execution time to solve these problems. In this way we obtain new proofs of some well known results and some new ones. The last part gives impossibility results on the existence of Las Vegas distributed algorithms to break symmetries at distance k for k ≥ 3.

In this paper we extend the notion of indifferentiability to some class of probabilistic algorithms. The extension is natural and focuses on cases in which algorithm’s execution time does not depend on algorithm’s input. This extension allows us to generalize the framework of admissible encodings onto elliptic curves (known from CRYPTO 2010) to some class of non-deterministic mapping algorithms. Using Siguna’s Müller probabilistic square root algorithm and the framework generalized we show a single mapping that works efficiently for any finite field Fq of characteristic greater than 3, and that is immune to timing attacks. In a result we remove limitations of the mappings analyzed in the CRYPTO 2010 paper: for finite fields Fq of characteristic greater than 3 the mappings analyzed there work only if q = 2 mod 3 or q = 3 mod 4. Consequently, we remove limitations of PACE v2 Integrated Mapping used in Supplemental Access Control.

Let A, B, and C be nxn matrices of integer numbers. We show that there is a deterministic algorithm of quadratic time complexity (w.r.t. the number of arithmetical operations) verifying whether $\A\B=\C.$ For the integer matrices this result improves upon the best known result by Freivalds from 1977 that only holds for a randomized (Monte Carlo) algorithm. As a consequence, we design a quadratic time nondeterministic integer matrix multiplication algorithm whose time complexity cannot be further improved. This indicates that any technique for proving a super-quadratic lower bound for deterministic matrix multiplication must exploit methods which would not work for the non-deterministic case.

Many of software engineering tools and systems are focused to monitoring source code quality and optimizing software development. Many of them use similar source code metrics to solve different kinds of problems. This inspired us to propose an environment for platform independent code monitoring, which supports employment of multiple source code monitoring tools and sharing of information among them to reduce redundant calculations. In this paper we present design of an architecture of the environment, whose main contribution is employing (acquiring, generating and processing) information tags –- descriptive metadata that indirectly refer source code artifacts, project documentations and developers activity via document models and user models. Information tags represent novel concept unifying traditional content based software metrics with recently developed activity-based metrics. We also describe prototype realization of the environment within project PerConIK (Personalized Conveying Information and Knowledge), which proves feasibility and usability of the proposed environment.

We present an optimal, truly linear time algorithm for the shortest unique substring problem, thus improving the algorithm by Pei et al. (ICDE 2013). Our implementation is simple and based on suffix arrays. Computational experiments show that our algorithm is much more efficient in practice, compared to that of Pei et al.

Currently nearly all commercial and open source BPMS are based on BPMN as a process notation. In contrast, the paper proposes to build a BPMS based on a domain specific language (DSL) as a process notation – DSBPMS. In such a DSBPMS a specific business process support could be created by business analysts. A platform for creating such DSBPMS with feasible efforts is described. This platform contains a Configurator for easy creation of graphical editors for the chosen DSL and a simple mapping language for transforming processes in this DSL to a language directly executable by the execution engine of this platform. The engine includes also all typical execution support functions so no other tools are required.

We study the 3-dimensional Strip Packing problem: Given a list of n boxes b_1,...,b_n of the width w_i\leq 1, depth d_i\leq 1 and an arbitrary length l_i. The objective is to pack all boxes into a strip of the width and depth 1 and infinite length, so that the packing length is minimized. The boxes may not overlap or be rotated. We present an improvement of the current best asymptotic approximation ratio of 1.692 by Bansal et al. with an asymptotic 3/2+\eps-approximation for any \eps>0.

Most automobile manufacturers maintain many vehicle types to keep a successful position on the market. Through the further development all vehicle types gain a diverse amount of new functionality. Additional features have to be supported by the car's software. For time efficient accomplishment, usually the existing electronic control unit (ECU) code is extended.

In the majority of cases this evolutionary development process is accompanied by a constant decay of the software architecture. This effect known as software erosion leads to an increasing deviation from the requirements specifications. To counteract the erosion it is necessary to continuously restore the architecture in respect of the specification.

Automobile manufacturers cope with the erosion of their ECU software with varying degree of success. Successfully we applied a methodical and structured approach of architecture restoration in the specific case of the brake servo unit (BSU). Software product lines from existing BSU variants were extracted by explicit projection of the architecture variability and decomposition of the original architecture. After initial application, this approach was capable to restore the BSU architecture recurrently.

Agile methodologies have impact not only on coding, but also on requirements engineering activities. In the paper agile requirements engineering is examined from the research point of view. It is claimed that use cases are a better tool for requirements description than user stories as they allow zooming through abstraction levels, can be reused for user manual generation, and when used properly can provide quite good effort estimates. Moreover, as it follows from recent research, parts of use cases (namely event descriptions) can be generated in an automatic way. Also the approach to non-functional requirements can be different. Our experience shows that they can be elicited very fast and can be quite stable.

In several areas of computing, the problem instance contains some entities not known to the algorithm (e.g., a communication topology in distributed computing, a sequence of future requests in online computing), and it is often the case that a complete knowledge of these parameters would make the problem solvable easily. A natural question is to ask to what extend some limited information about the unknown variables may help. Traditionally, the approach is to study the impact of the knowledge of various specific properties (e.g., the communication algorithm may be equipped with a sense of direction; the online algorithm may know that the requests have certain structure, etc.). Recently, a quantitative approach has been pursued, in which the algorithm may be equipped with an arbitrary information (best case), and the relationship between the size of this information, and the performance of the algorithm is studied. The talk surveys recent results in this setting.

Most conceptual modeling and knowledge representation schemes focus on relations. The Entity-Relationship approach is a paradigmatic example in this respect. However, in many cases, when we say that a relationship holds (say, John is married with Mary) there is something which occurs (or "perdures") in a certain interval of time. Technically speaking, this entity is a perdurant, in DOLCE's terms. We may call it an event for short, in the most general understanding of this term, but I tend to prefer the term episode, for the reasons I will illustrate in my talk (according to OALD, an episode is "an event, a situation, or a period of time that is important or interesting in some way").

My main point will be that, whenever there is an episode which corresponds to a particular relationship, it is very useful to model such episode explicitely, putting it in the domain of discourse. I will investigate the various cases when a relationship corresponds to an episode, and illustrate a number of open ontological issues concerning episodes and their participants.