International Journal of Foundations of Computer Science

In this paper we study an online minimum makespan scheduling problem with a reordering buffer. We obtain the following results: (i) for m > 51 identical machines, we give a 1.5-competitive online algorithm with a buffer of size ⌈1.5m⌉; (ii) for three identical machines, we give an optimal online algorithm with a buffer size six, better than the previous nine; (iii) for m uniform machines, using a buffer of size m, we improve the competitive ratio from 2 + ε to 2 − 1/m+ ε, where ε > 0 is sufficiently small and m is a constant.

Constructing 2m-variable Boolean functions with optimal algebraic immunity based on decomposition of additive group of the finite field seems to be a promising approach since Tu and Deng's work. In this paper, we consider the same problem in a new way. Based on polar decomposition of the multiplicative group of , we propose a new construction of Boolean functions with optimal algebraic immunity. By a slight modification of it, we obtain a class of balanced Boolean functions achieving optimal algebraic immunity, which also have optimal algebraic degree and high nonlinearity. Computer investigations imply that this class of functions also behaves well against fast algebraic attacks.

Communication networks must be constructed to be as stable as possible, not only with the respect to the initial disruption, but also with respect to the possible reconstruction. Many graph theoretical parameters have been used to describe the stability of communication networks. Tenacity is a reasonable one, which shows not only the difficulty to break down the network but also the damage that has been caused. Total graphs are the largest graphs formed by the adjacent relations of elements of a graph. Thus, total graphs are highly recommended for the design of interconnection networks. In this paper, we determine the tenacity of the total graph of a path, cycle and complete bipartite graph, and thus give a lower bound of the tenacity for the total graph of a graph.

Location verification in wireless sensor networks (WSNs) is quite challenging in the presence of malicious sensor nodes, which are called attackers. These attackers try to break the verification protocol by reporting their incorrect locations during the verification stage. In the literature of WSNs, most of the existing methods of location verification use a set of trusted verifiers, which are vulnerable to attacks by malicious nodes. These existing methods also use some distance estimation techniques, which are not accurate in noisy channels. In this article, we adopt a statistical approach for secure location verification to overcome these limitations. Our proposed method does not rely on any trusted entities and it takes care of the limited precision in distance estimation by using a suitable probability model for the noise. The resulting verification scheme detects and filters out all malicious nodes from the network with a very high probability even when it is in a noisy channel.

Looking at the automata defined over a group alphabet as a nearring, we see that they are a highly complicated structure. As with ring theory, one method to deal with complexity is to look at semisimplicity modulo radical structures. We find some bounds on the Jacobson 2-radical and show that in certain groups, this radical can be explicitly found and the semisimple image determined.

The AREA of a schedule for executing DAGs is the average number of DAG-chores that are eligible for execution at each step of the computation. AREA maximization is a new optimization goal for schedules that execute DAGs within computational environments, such as Internet-based computing, clouds, and volunteer computing projects, that are dynamically heterogeneous, in the sense that the environments' constituent computers can change their effective powers at times and in ways that are not predictable. This paper is motivated by the thesis that, within dynamically heterogeneous environments, DAG-schedules that have larger AREAs execute a computation-DAG with smaller completion time under many circumstances; this thesis is supported by preliminary simulation-based experiments. While every DAG admits an AREA-maximizing schedule, it is likely computationally difficult to find such a schedule for an arbitrary DAG. Earlier work has shown how to craft AREA-maximizing schedules efficiently for a number of families of DAGs whose structures are reminiscent of many scientific computations. The current paper extends this work by showing how to efficiently craft AREA-maximizing schedules for series-parallel DAGs, a family that models a multithreading computing paradigm. The techniques for crafting these schedules promise to apply also to other large families of recursively defined DAGs. Moreover, the ability to derive these schedules efficiently leads to an efficient AREA-oriented heuristic for scheduling arbitrary DAGs.

In geometric covering problems, the aim is to cover a set of given points using a minimum number of shapes with prescribed properties. These problems extend in many ways such as covering in the presence of obstacles and partial covering. Since in most cases these problems are NP-hard, researchers have developed a large number of approximation algorithms to solve them.

In this paper, with a more general view on these approaches, we propose an algorithmic framework that gives an approximation algorithm for the covering problem at hand, provided that its prerequisites are satisfied. As the result, we present a general class of geometric covering problems for which one can obtain polynomial-time approximation schemes (PTASs). This class of problems involves covering point sets with bounded shapes in a space with fixed dimension. For a problem to be in this class, it must be possible to find a polynomial number of maximal shapes and it must be possible to cover all the points in a small box with a small number of shapes.

Using this framework, we present two new PTASs for the problems of covering with disks in the presence of polygonal obstacles and covering with sectors (pie-shaped wedges). The first problem has never been addressed before and for the second problem, only a logarithmic approximation algorithm was known in general and a 9-approximation algorithm for wide angles.

Nested words have been introduced by Alur and Madhusudan as a model for e.g. recursive programs or XML documents and have received much recent interest. In this paper, we investigate a quantitative automaton model and a quantitative logic for nested words. The behavior resp. the semantics map nested words to weights which are taken from a strong bimonoid. Strong bimonoids can be viewed as semirings without requiring the distributivity assumption which was essential in the classical theory of formal power series; strong bimonoids include e.g. all bounded lattices and many other structures from multi-valued logics. Our main results show that weighted nested word automata and suitable weighted MSO logics are expressively equivalent. This extends the classical Büchi-Elgot result from words to a weighted setting for nested words.