Ricerc@Sapienza

We study the design of cost-sharing protocols for two fundamental resource allocation problems, the Set Cover and the Steiner Tree Problem, under environments of incomplete information (Bayesian model). Our objective is to design protocols where the worst-case Bayesian Nash equilibria have low cost, i.e. the Bayesian Price of Anarchy (PoA) is minimized. Although budget balance is a very natural requirement, it puts considerable restrictions on the design space, resulting in high PoA. We propose an alternative, relaxed requirement called budget balance in the equilibrium (BBiE).

This paper presents an image fusion method which uses an image dependent multiscale decomposition and a fusion rule which is based on the local image multiscale activity. The latter is used for determining a proper partition of the frequency plane where the max-based fusion strategy is applied; the same image activity is used for guiding the max-based fusion rule. Multiscale local image activity is computed using an estimation of the local Lipschitz regularity at different resolutions.

In this paper local and non-local denoising methods are jointly employed in order to improve the visual quality of the final denoised image. Based on the evidence that the output images of non local denoising methods are not pointwise better everywhere than the outputs images of local methods and than the noisy image itself, the cascade of two improvement steps is applied to the output image of a non local denoising method. The first step aims at correcting the output image by recovering the lost information directly from the noisy one.

We consider an anisotropic hyperbolic equation with memory term: ?t2u(x,t)=?i,j=1n?i(aij(x)?ju)+?0t?|?|?2b?(x,t,?)?x?u(x,?)d?+R(x,t)f(x) for $x \in \Omega$ and $t\in (0, T)$ , which is a simplified model equation for viscoelasticity. The main result is a both-sided Lipschitz stability estimate for an inverse source problem of determining a spatial varying factor $f(x)$ of the force term $R(x, t)\,f(x)$ .

Given an action ? of a discrete group G on a unital C?-algebra A, we
introduce a natural concept of ?-negative definiteness for functions from G to A,
and examine some of the first consequences of such a notion. In particular, we prove
analogs of theorems due to Delorme–Guichardet and Schoenberg in the classical case
where A is trivial. We also give a characterization of the Haagerup property for the
action ? when G is countable.

The paper presents a method for color quantization (CQ)which uses visual contrast for determining an image-dependent colorpalette. The proposed method selects image regions in a hierarchicalway, according to the visual importance of their colors with respect to thewhole image. The method is automatic, image dependent and requires amoderate computational effort. Preliminary results show that the qual-ity of quantized images, measured in terms of Mean Square Error, ColorLoss and SSIM, is competitive with some existing CQ approaches.

Declarative process mining is the set of techniques aimed at extracting behavioural constraints from event logs. These constraints are inherently of a reactive nature, in that their activation restricts the occurrence of other activities. In this way, they are prone to the principle of ex falso quod libet: they can be satisfied even when not activated. As a consequence, constraints can be mined that are hardly interesting to users or even potentially misleading.

A graph G = (V,E) is a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers dminand dmax, dmin≤ dmax, such that each node u∈V is uniquely associated to a leaf of T and there is an edge (u, v) ∈ E if and only if dmin≤ dT(u, v) ≤ dmax, where dT(u, v) is the sum of the weights of the edges on the unique path PT(u, v) from u to v in T. Understanding which graph classes lie inside and which ones outside the PCG class is an important issue. Despite numerous efforts, a complete characterization of the PCG class is not known yet.

We characterize several complexity measures for the resolution of Tseitin formulas in terms of a two person cop-robber game. Our game is a slight variation of the one Seymour and Thomas used in order to characterize the tree-width parameter. For any undirected graph, by counting the number of cops needed in our game in order to catch a robber in it, we are able to exactly characterize the width, variable space and depth measures for the resolution of the Tseitin formula corresponding to that graph. We also give an exact game characterization of resolution variable space for any formula.

The identification and classification of bio-chemical substances are very important tasks in chemical, biological and forensic analysis. In this work we present a new strategy to improve the accuracy of the supervised classification of this type of data obtained from different analytical techniques that combine two processes: first, a dissimilarity representation of data and second, the selection of templates for the refinement of the representative samples in each class set. In order to evaluate the performance of our proposal, a comparative study between three approaches is presented.