Rapporti tecnici

This technical report presents a new partial order of a set A of alternatives according to a set of criteria C.<br />The order is based on a binary strict preference relation that is not transitive but that satisfies asymmetry. The order corresponds to a directed graph as an aiding tool to allow the single decision maker to select the best alternative from the set A.

FastFlow is a structured parallel programming framework targeting shared memory multicore architectures. Its layered design and the optimized implementation of the communication mechanisms used to implement the FastFlow streaming networks provided to the application programmer as algorithmic skeletons support the development of efficient fine grain applications.<br />FastFlow is available at http://sourceforge.net/projects/mc-fastflow/. <br />This work introduces FastFlow programming techniques and points out the different ways used to parallelize existing C/C++ code using FastFlow as a software accelerator. In short: this is a kind of tutorial on FastFlow.<br />

In this paper we study the Near-Gathering problem for a set of asynchronous, anonymous, oblivious and autonomous mobile robots with limited visibility moving in Look-Compute-Move (LCM) cycles: In this problem, the robots have to get close enough to each other, so that every robot can see all the others, without touching (i.e., colliding) with any other robot. <br />The importance of this problem might not be clear at a first sight: Solving the Near-Gathering problem, it is possible to overcome the limitations of having robots with limited visibility, and it is therefore possible to exploit all the studies (the majority, actually) done on this topic, in the unlimited visibility setting. In fact, after the robots get close enough, they are able to see all the robots in the system, a scenario similar to the one where the robots have unlimited visibility. Here, <br />we present a collision-free algorithm for the Near-Gathering problem, the first to our knowledge, that allows a set of autonomous mobile robots to nearly gather within finite time. The collision-free feature of our solution is crucial in order to combine it with an unlimited visibility protocol. In fact, the majority of the algorithms that can be found on the topic assume that all robots occupy distinct positions at the beginning. Hence, only providing a collision-free Near-Gathering algorithm, as the one presented here, is it possible to successfully combine it with an unlimited visibility protocol, hence overcoming the natural limitations of the limited visibility scenario.<br />In our model, distances are induced by the infinity norm. A discussion on how to extend our algorithm to models with different distance functions, including the usual Euclidean distance, is also presented.

Traditional process calculi usually abstract away from network details, modeling only communication over shared channels. They, however, seem inadequate to describe new network architectures, such as Software Defined Networks, where programs are allowed to manipulate the infrastructure. In this paper we present a network conscious, proper extension of the pi-calculus: we add connector names and the primitives to handle them, and we provide both an interleaving and a concurrent semantics. The extension to connector names is natural and seamless, since they are handled in full analogy with ordinary names. In the interleaving case, observations are the routing paths through which sent and received data are transported, while in the concurrent case we allow to observe multisets of paths. However, restricted connector names do not appear in the observations, which thus can possibly be as abstract as in the pi-calculus. Finally, for the concurrent semantics we show that bisimilarity is a congruence, and this property holds also for the concurrent version of the pi-calculus.

We discuss a numerical algorithm for minimization of a convex nondifferentiable function belonging to the family of proximal bundle methods. Unlike all of its brethren, the approach does not rely on measuring descent of the objective function at the so-called ``serious steps'', while ``null steps'' only serve at improving the descent direction in case of unsuccessful steps. Rather, a merit function is defined which is decreased at each iteration, leading to a (potentially) continuous choice of the stepsize between zero (the null step) and one (the serious step). By avoiding the discrete choice the convergence analysis is simplified, and we can more easily obtain efficiency estimates for the method. Simple choices for the step selection actually reproduce the dichotomic 0/1 behavior of standard proximal bundle methods, but shedding new light on the rationale behind the process, and ultimately with different rules. Yet, using nonlinear upper models of the function in the step selection process can lead to actual fractional steps.

In this technical report we present a method that can be used by a set of decison makers in order to rank a certain number of alternatives according to a given set of criteria. The method aims at producing a directed multigraph involving all the alternatives so that it is possible for the decison makers to identify the worst alternatives and the best alternatives. The worst alternatives are never selected by the decision makers that perform their final selection among teh best aletrnatives. <br />

Given a set of integer keys from a bounded universe along with associated data, the dictionary problem asks to answer two queries: membership and retrieval. Membership has to tell whether a given element is in the dictionary or not; retrieval has to return the data associated with the searched key. This paper studies three well-established relaxations of this basic problem: (Compressed) Static functions, Approximate membership and Relative membership. (Compressed) Static functions. In this relaxation, also known as retrieval-only dictionaries, we are given a set $S \subseteq U$ of $n$ integers and each of them has associated data from an alphabet of size $\sigma$. The problem asks to build a dictionary that, given a key $x\in S$, returns its associate data. Notice that, whenever $x \not \in S$, arbitrary data is returned. This problem has been widely studied in the past. Solutions to this problem have to carefully organize associated data, so that, they can be retrieved in constant time without the need of storing keys in $S$. Compressed static functions move a step forward: not only do not store the keys, but also achieve space complexities bounded in term of the entropy $H_0$ of the associated data. Such kind of solutions are very interesting mainly for two reasons. Firstly, being $nH_0$ at most $n\log \sigma$, these results are always at least as good as the uncompressed ones. Moreover, since the associated data often follow a skewed distribution, $nH_0$ could even become sublinear in $n$. The current best solutions are by Porat and Hreinsson et al. The first one requires $n\log \sigma +o(n)$ bits of space, while the second one uses $(1+\delta)nH_0+n \cdot \min(p_0+0.086,1.82(1-p_0))$ bits of space, where $p_0$ is the probability of the most frequent symbol and $\delta$ is a constant greater than $0$. Thus, the space complexities of these solutions are incomparable: the former has a sublinear overhead but is not compressed, while the latter is suboptimal due to the factor $(1+\delta)$ to multiply $H_0$ and has an overhead that may be $\Theta(n)$ depending on $p_0$. Our optimal scheme achieves the best of the two being the first known solution obtaining simultaneously constant query time, compressed space ($nH_0$), and sublinear overhead ($o(n)$). We strongly believe that these characteristics makes the use of static functions significantly more appealing for many applications. Approximate membership. The approximate membership problem has been studied for decades and the Bloom filter data structure~is probably the most popular and widely used technique solving it. With Bloom filters we can represent a set of $n$ integers by using $n\log\frac{1}{\epsilon} \log e$ bits of space with false positive probability ({\sf fpp}) $\epsilon$. Both its space and time complexities are non-optimal: space is a constant factor away from optimal, and query time is logarithmic in $\frac{1}{\epsilon}$. Constant time approximate membership data structures are able to achieve optimal $n \log \frac{1}{\epsilon} +o(n)$ bits of space only if $\frac{1}{\epsilon}$ is a power of two. The current best solution requires an $O(n)$ bits overhead in addition to the optimal space, for an arbitrary {\sf fpp}. Our optimal scheme is the first known solution having $o(n)$ overhead, for any value of $\epsilon$ such that $\log \frac{1}{\epsilon} = o(\log n / \log\log n)$, namely, any reasonable choice of $\epsilon$ in practice. Relative membership. This problem asks to solve a further relaxation of the membership query. Given two sets $S$ and $R$ with $S \subset R$, we must be able to distinguish whether a key belongs to $S$ or $R\setminus S$. Our compressed static functions are used to obtain a constant time solution for the problem achieving an optimal space complexity (up to lower order term).

Equilibrium problems provide a mathematical framework which includes optimization, variational inequalities, fixed-point and saddle point problems, and noncooperative games as particular cases. This general format received an increasing interest in the last decade mainly because many theoretical and algorithmic results developed for one of these models can be often extended to the others through the unifying language provided by this common format. This survey paper aims at covering the main results concerning the existence of equilibria and the solution methods for finding them.<br />

FGCJ is a minimal core calculus that extends Featherweight Generic Java, FGJ, with lambda expressions for Java Simple Closures. It has been introduced to study, in a reduction semantics framework, properties of Java Simple Closures, including type safety and abstraction property. F is a source-to-source, translation rule system from Java 1.5 extended with lambda expressions, back to ordinary Java 1.5. It has been introduced to study, in a translation semantics framework, the design and the implementation features of lambda expressions, including simple closures, this transparency, non local variables and relations with anonymous class objects. In this paper we prove that the reduction semantics and the translation semantics commute in FGACJ. Where FGACJ is a minimal core calculus that extends FGCJ, by adding Java interfaces and anonymous class objects and that allows a restricted definition of translation semantics F.

This paper deals with equilibrium problems with nonlinear constraints. Exploiting the gap function recently introduced by the authors, which rely on a polyhedral approximation of the feasible region, we propose two descent methods. They are both based on the minimization of a suitable exact penalty function, but they use different rules for updating the penalization parameter and they rely on different types of line search. The convergence of both algorithms is proved under standard assumptions.

Opportunistic computing is an exciting evolution of opportunistic networks. The services provision in these networks suffer from the limitations of conventional MANETs such as non stable connections and limited distribution of knowledge between nodes. The introduction of services composition introduces new challenges for the definition of a system able to recognize the best alternative to choose from. The nodes in the network have heterogeneous physical characteristics, different mobility patterns and executes a variety of different services. During the connection, pairs of nodes may collaborate by exchanging information on the network status, such as characteristics of the encountered nodes and workload of their nodes. We propose a system which is capable of processing such information in order to offer the best alternative for a service request. The selection algorithms evaluate services composition by considering alternative paths. In this paper we analyze two types of knowledge distribution strategies to study sequential compositions in opportunistic networks. We propose an analytical model which is validated through a set of simulations, verifying the properties set.

In this paper we study the structure of almost normal matrices, that is the matrices for which there exists a rank-one matrix $C$ such that $A^HA-AA^H=CA-AC$. Necessary and sufficient conditions for a matrix to belong to the class are given and a canonical representation as a block tridiagonal matrix is shown. The approach is constructive and in the paper it is explained how, starting from a $1\times 1$ or $2\times 2$ matrix we can generate almost normal matrices. Moreover, given an $n\times n$ almost normal matrix we can compute the block tridiagonal representation with a finite procedure.<br /><br />

We propose a version of the (generalized) bundle scheme for convex nondifferentiable optimization suitable for the case of a sum-function where some of the components are &quot;easy&quot;, that is, they are Lagrangian functions of explicitly known compact convex programs. This corresponds to a <i>stabilized partial Dantzig-Wolfe decomposition</i>, where suitably modified representations of the &quot;easy&quot; convex subproblems are inserted in the master problem as an alternative to iteratively inner-approximating them by extreme points, thus providing the algorithm with exact information about a part of the dual objective function. The resulting master problems are potentially larger and less well-structured than the standard ones, ruling out the available specialized techniques and requiring the use of general-purpose solvers for their solution; this strongly favors piecewise-linear stabilizing terms, as opposed to the more usual quadratic ones. This in turn may have an adverse effect on the convergence speed of the algorithm, so that the overall performance may depend on appropriate tuning of all these aspects. Yet, very good computational results are obtained in at least one relevant application: the computation of tight lower bounds for Fixed-Charge Multicommodity Min-Cost Flow problems. <br /><br />