Archivio della ricerca dell'UniversitÃ di Modena e Reggio Emiliahttps://iris.unimore.itIl sistema di repository digitale IRIS acquisisce, archivia, indicizza, conserva e rende accessibili prodotti digitali della ricerca.Tue, 23 Jul 2019 05:38:54 GMT2019-07-23T05:38:54Z10701K-Boost: a Scalable Algorithm for High-Quality Clustering of Microarray Gene Expression Datahttp://hdl.handle.net/11380/612899Titolo: K-Boost: a Scalable Algorithm for High-Quality Clustering of Microarray Gene Expression Data
Abstract: In this paper we propose K-Boost, a novel clustering algorithm basedon a combination of the Furthest-Point-First (FPF) heuristic for solving themetric k-center problem, a {\em stability-based} method for determining thenumber of clusters, and a k-means-like cluster refinement. Experiments showthat \textit{K-Boost} exhibits a good quality/running time tradeoff that makesit ideal for large data sets, with quality measured by several internal andexternal criteria.
Thu, 01 Jan 2009 00:00:00 GMThttp://hdl.handle.net/11380/6128992009-01-01T00:00:00ZThe k-neighbors approach to interference bounded and symmetric topology control in ad hoc networkshttp://hdl.handle.net/11380/303969Titolo: The k-neighbors approach to interference bounded and symmetric topology control in ad hoc networks
Abstract: Topology control, wherein nodes adjust their transmission ranges to conserve energy and reduce interference, is an important feature in wireless ad hoc networks. Contrary to most of the literature on topology control which focuses on reducing energy consumption, in this paper we tackle the topology control problem with the goal of limiting interference as much as possible, while keeping the communication graph connected with high probability. Our approach is based on the principle of maintaining the number of physical neighbors of every node equal to or slightly below a specific value k. As we will discuss in this paper, having a nontrivially bounded physical node degree allows a network topology with bounded interference to be generated. The proposed approach enforces symmetry on the resulting communication graph, thereby easing the operation of higher layer protocols. To evaluate the performance of our approach, we estimate the value of k that guarantees connectivity of the communication graph with high probability both theoretically and through simulation. We then define k-NEIGH, a fully distributed, asynchronous, and localized protocol that uses distance estimation. k-NEIGH guarantees logarithmically bounded physical degree at every node, is the most efficient known protocol (requiring 2n messages in total, where n is the number of nodes in the network), and relies on simpler assumptions than existing protocols. Furthermore, we verify through simulation that the network topologies produced by k-NEIGH show good performance in terms of node energy consumption and expected interference.
Sun, 01 Jan 2006 00:00:00 GMThttp://hdl.handle.net/11380/3039692006-01-01T00:00:00ZAn Efficient Algorithm for Planted Composit Motif Extractionhttp://hdl.handle.net/11380/618362Titolo: An Efficient Algorithm for Planted Composit Motif Extraction
Abstract: In this paper we present an algorithm for the problem of planted structured motif extraction from a set of sequences. This problem is strictly related to the structured motif extraction problem, which has many important applications in molecular biology. We propose an algorithm that uses a simple two-stage approach: first it extracts simple motifs, then the simple motifs are combined in order to extract structured motifs. We compare our algorithm with existing algorithms whose code is available, and which are based on more complex approaches. Our experiments show that, even if in general the problem is NP-hard, our algorithm is able to handle complex instances of the problem in a reasonable amount of time.
Thu, 01 Jan 2009 00:00:00 GMThttp://hdl.handle.net/11380/6183622009-01-01T00:00:00ZParallel Algebraic Reductions among Numerical Problemshttp://hdl.handle.net/11380/454052Titolo: Parallel Algebraic Reductions among Numerical Problems
Abstract: In this note we consider, for a number of linear algebra problems, an environmentallowing approximate computations. Within this framework we show that the relative complexity of these problems should be studied according to a strict notion of reducibility, which corresponds to the well-known many-one reducibility of combinatorial complexity.
Tue, 01 Jan 1991 00:00:00 GMThttp://hdl.handle.net/11380/4540521991-01-01T00:00:00ZAMBIT: Towards an Architecture for the Development of Context-dependent Applications and Systemshttp://hdl.handle.net/11380/1035120Titolo: AMBIT: Towards an Architecture for the Development of Context-dependent Applications and Systems
Abstract: The development of ubiquitous services tailored to the needs
and expectations of a very large number of potential users (especially
mobile users) requires that future applications and systems be aware of
the service fruition contexts and possibly of accurate user proles.
The AMBIT research project aims at providing a general model of con-
text as well as a platform that can be exploited to build and deploy dif-
ferent kinds of context-dependent applications and systems. We aim at
overcoming the restrictions of the existing approaches, which are mainly
due to the limited notion of context they propose (if any). In partic-
ular, we stress the fact that current technologies does not accurately
consider the notion of context semantics and user prole, which is the
main source of the
ooding of useless data that overload systems and
often users' minds.
Wed, 01 Jan 2014 00:00:00 GMThttp://hdl.handle.net/11380/10351202014-01-01T00:00:00ZParallel Complexity of Householder QR Factorizationhttp://hdl.handle.net/11380/641690Titolo: Parallel Complexity of Householder QR Factorization
Abstract: Gaussian Elimination with Partial Pivoting and Householder QRfactorization are two very popular methods to solve linear systems.Implementations of these two methods are provided in state-of-the-artnumerical libraries and packages, such as LAPACK and MATLAB.Gaussian Elimination with Partial Pivoting was already known to beP-complete. Here we prove that the Householder QR factorization islikely to be inherently sequential as well. We also investigate theproblem of speedup vs non degeneracy and accuracy in numericalalgorithms.
Mon, 01 Jan 1996 00:00:00 GMThttp://hdl.handle.net/11380/6416901996-01-01T00:00:00ZRepeated Matrix Squaring for the Parallel Solution of Linear Systemshttp://hdl.handle.net/11380/641691Titolo: Repeated Matrix Squaring for the Parallel Solution of Linear Systems
Abstract: Given a nxn nonsingular linear system Ax=b, we prove that thesolution x can be computed in parallel time ranging from Omega(logn) to O(log^2 n), provided that the condition number, c(A), of A isbounded by a polynomial in n. In particular, if c(A) = O(1), a timebound O(log n) is achieved. To obtain this result, we reduce thecomputation of x to repeated matrix squaring and prove that a numberof steps independent of n is sufficient to approximate x up to arelative error 2^â€“d, d=O(1). This algorithm has both theoretical andpractical interest, achieving the same bound of previously publishedparallel solvers, but being far more simple.
Wed, 01 Jan 1992 00:00:00 GMThttp://hdl.handle.net/11380/6416911992-01-01T00:00:00ZCNVScan: detecting borderline copy number variations in NGS data via scan statisticshttp://hdl.handle.net/11380/1072992Titolo: CNVScan: detecting borderline copy number variations in NGS data via scan statistics
Thu, 01 Jan 2015 00:00:00 GMThttp://hdl.handle.net/11380/10729922015-01-01T00:00:00ZEfficient computation of Nash equilibria for very sparse win-lose bimatrix gameshttp://hdl.handle.net/11380/641688Titolo: Efficient computation of Nash equilibria for very sparse win-lose bimatrix games
Abstract: It is known that finding a Nash equilibrium for win-lose bimatrixgames, i.e., two-player garnes where the players' payoffs are zero andone, is complete for the class PPAD. We describe a linear timealgorithm which computes a Nash equilibrium for win-lose bimatrixgarnes where the number of winning positions per strategy of each ofthe players is at most two. The algorithm acts on the directed graphthat represents the zero-one pattern of the payoff matrices describingthe game. It is based upon the efficient detection of certain subgraphswhich enable us to determine the support of a Nash equilibrium.
Sat, 01 Jan 2005 00:00:00 GMThttp://hdl.handle.net/11380/6416882005-01-01T00:00:00ZDistributed Algorithm for a Color Assignment on Asynchronous Ringshttp://hdl.handle.net/11380/308115Titolo: Distributed Algorithm for a Color Assignment on Asynchronous Rings
Abstract: We study a version of the beta-assignment problem (Chang and Lee, 1988) on asynchronous rings: consider a set of items and a set of m colors, where each item is associated to one color. Consider also n computational agents connected by an asynchronous ring. Each agent holds a subset of the items, where initially different agents might hold items associated to the same color. We analyze the problem of distributively assigning colors to agents in such a way that (a) each color is assigned to one agent and (b) the number of different colors assigned to each agent is minimum. Since any color assignment requires that the items be distributed according to it (e.g. all items of the same color are to be held by only one agent), we define the cost of a color assignment as the amount of items that need to be moved, given an initial allocation. We first show that any distributed algorithm for this problem on the ring requires a communication complexity of Omega(n middot m) and then we exhibit a polynomial time distributed algorithm with message complexity matching the bound, that determines a color assignment with cost at most (2 + eps) times the optimal cost, for any 0 < eps < 1.
Sun, 01 Jan 2006 00:00:00 GMThttp://hdl.handle.net/11380/3081152006-01-01T00:00:00Z