The proceedings contains 155 papers from the applied computing 2004 - proceedings of the 2004 acm symposium on applied computing: Vol 1. Topics discussed include: person identification from heavily occluded face image...
详细信息
The proceedings contains 155 papers from the applied computing 2004 - proceedings of the 2004 acm symposium on applied computing: Vol 1. Topics discussed include: person identification from heavily occluded face images;morphing of image represented objects using a physical methodology;hierarchical nonlinear constraint satisfaction;concatenate feature extraction for robust 3D elliptic object localization' symbol representation in map image compression;and solving weighted max-sat optimization problems using a taboo scatter search.
The proceedings contains 135 papers from the appliedcomputing2004-proceedings of the 2004acmsymposium on appliedcomputing : Volume 2. The topics discussed include: issues of pedagogy and design in e-learning syst...
详细信息
The proceedings contains 135 papers from the appliedcomputing2004-proceedings of the 2004acmsymposium on appliedcomputing : Volume 2. The topics discussed include: issues of pedagogy and design in e-learning systems;patterns for blended, person-centered learning: strategy, concepts, experiences, and evaluation;an architecture for supporting vicarious learning in a distributed environment;modeling and execution of e-learning resources;using a genetic algorithm to optimize the gape of a snake jaw;shadow document methods of results merging and ontology and rule based retrieval of sound objects in augmented audio reality system for museum visitors.
Motivated by the problem of routing reliably and scalably in a graph, we introduce the notion of a splicer, the union of spanning trees of a graph. We prove that for any bounded-degree n-vertex graph, the union of two...
详细信息
Motivated by the problem of routing reliably and scalably in a graph, we introduce the notion of a splicer, the union of spanning trees of a graph. We prove that for any bounded-degree n-vertex graph, the union of two random spanning trees approximates the expansion of every cut of the graph to within a factor of O(log n). For the random graph G_(n,p), for p = Ω(log n/n), we give a randomized algorithm for constructing two spanning trees whose union is an expander. This is suggested by the case of the complete graph, where we prove that two random spanning trees give an expander. The construction of the splicer is elementary; each spanning tree can be produced independently using an algorithm by Aldous and Broder: A random walk in the graph with edges leading to previously unvisited vertices included in the tree. Splicers also turn out to have applications to graph cut-sparsification where the goal is to approximate every cut using only a small subgraph of the original graph. For random graphs, splicers provide simple algorithms for sparsifiers of size O(n) that approximate every cut to within a factor of O(log n).
We propose Compressed Counting (CC) for approximating the αth frequency moments (0 < α≤2) of data streams under a relaxed strict-Turnstile model, using maximally-skewed stable random projections. Estimators base...
详细信息
We propose Compressed Counting (CC) for approximating the αth frequency moments (0 < α≤2) of data streams under a relaxed strict-Turnstile model, using maximally-skewed stable random projections. Estimators based on the geometric mean and the harmonic mean are developed. When α = 1, a simple counter suffices for counting the first moment (i.e., sum). The geometric mean estimator of CC has asymptotic variance ∝ Δ = |α-1|, capturing the intuition that the complexity should decrease as Δ=|α-1|→0. However, the previous classical algorithms based on symmetric stable random projections[12, 15] required O(1/ε~2) space, in order to approximate the αth moments within a 1+ε factor, for any 0 < α≤2 including α = 1. We show that using the geometric mean estimator, CC requires O(1/(log (1+ε))+2Δ~(1/2)/((log(1+ε))~(3/2))+o(Δ~(1/2))) space, as Δ→0. Therefore, in the neighborhood of α = 1, the complexity of CC is essentially O (1/ε) instead of O(1/ε~2). CC may be useful for estimating Shannon entropy, which can be approximated by certain functions of the αth moments with α→1. [10, 9] suggested using α = 1+Δ with (e.g.,) Δ< 0:0001 and ε < 10~(-7), to rigorously ensure reasonable approximations. Thus, unfortunately, CC is "theoretically impractical" for estimating Shannon entropy, despite its empirical success reported in [16].
We consider the unsplittable flow problem on a line. In this problem, we are given a set of n tasks, each specified by a start time s_i, an end time t_i, a demand d_i > 0, and a profit p_i > 0. A task, if accept...
ISBN:
(纸本)9780898716740
We consider the unsplittable flow problem on a line. In this problem, we are given a set of n tasks, each specified by a start time s_i, an end time t_i, a demand d_i > 0, and a profit p_i > 0. A task, if accepted, requires d_i units of "bandwidth" from time s_i to t_i and accrues a profit of p_i. For every time t, we are also specified the available bandwidth c_t, and the goal is to find a subset of tasks with maximum profit subject to the bandwidth constraints. In this paper, we present the first polynomial-time O(log n)-approximation algorithm for this problem. No polynomial-time o(n)-approximation was known prior to this work. Previous results for this problem were known only in more restrictive settings, in particular, either if the given instance satisfies the so-called "no-bottleneck" assumption: max d_i ≤ min c_t, or else if the ratio of the maximum to the minimum demands and ratio of the maximum to the minimum capacities are polynomially (or quasi-polynomially) bounded in n. Our result, on the other hand, does not require any of these assumptions. Our algorithm is based on a combination of dynamic programming and rounding a natural linear programming relaxation for the problem. While there is an Ω(n) integrality gap known for this LP relaxation, our key idea is to exploit certain structural properties of the problem to show that instances that are bad for the LP can in fact be handled using dynamic programming.
The concept of entropy based on Shannon Theory of Information has been applied in the field of image processing and analysis since the work of T. Pun. This concept is based on the traditional Boltzaman-Gibbs entropy, ...
详细信息
The concept of entropy based on Shannon Theory of Information has been applied in the field of image processing and analysis since the work of T. Pun. This concept is based on the traditional Boltzaman-Gibbs entropy, proposed under the classical thermodynamic. On the other hand, it is well known that this old formalism fails to explain some physical system if they have complex behavior such as long rang interactions and long time memories. Recently, studies in mechanical statistics have proposed a new kind of entropy, called Tsallis entropy (or non-extensive entropy), which has been considered with promising results on several applications in order to explain such phenomena. The main feature of Tsallis entropy is the q-index parameter, which is close related to the degree of system nonextensivity. In 2004 was proposed the first algorithm for image segmentation based on Tsallis entropy. However, the computation of the q-index was already an open problem. On the other hand, in the field of image segmentation it is not an easy task to compare the quality of segmentation results. This is mainly due to the lack of an image ground truth based on human reasoning. In this paper, we propose the first methodology in the field of image segmentation for q-index computation and compare it with other similar approaches using a human based segmentation ground truth. The results suggest that our approach is a forward step for image segmentation algorithms based on Information Theory.
Differential quantities, including normals, curvatures, principal directions, and associated matrices, play a fundamental role in geometric processing and physics-based modeling. computing these differential quantitie...
详细信息
The increasing use of mobile devices and the dissemination of wireless networks have stimulated mobile and ubiquitous computing research. In this context, education is being considered one of the main application area...
详细信息
ISBN:
(纸本)9781595939470
The increasing use of mobile devices and the dissemination of wireless networks have stimulated mobile and ubiquitous computing research. In this context, education is being considered one of the main application areas. New pedagogical opportunities are created through the use of location systems to track learners, and through context awareness support. This paper proposes a model to explore these opportunities using location information and context management as learning support tools. This model, called LOCAL, was conceived for small scale learning environments, but can be applied in large-scale as well. The model was implemented and the initial results show its utility to assist the teaching and learning processes.
In this article, formal models for the data transmission mechanism between ARM and DSP cores of OMAP platform 161x via DSP Gateway are presented. These models are represented as timed automata. The automata for the be...
详细信息
ISBN:
(纸本)9781595937537
In this article, formal models for the data transmission mechanism between ARM and DSP cores of OMAP platform 161x via DSP Gateway are presented. These models are represented as timed automata. The automata for the behavior of tasks running in the DSP when receiving requests of read or write operations from ARM are described. Data transmission between ARM and DSP is modelled according to the mechanism offered by tokliBIOS, the system kernel at DSP side. The formal model presented in this work helps developers to understand the communication mechanisms of DSP Gateway and facilitates its usage and future development. Copyright 2008 acm.
暂无评论