the data migration problem is to compute an efficient plan for moving data stored on devices in a network from one configuration to another. It is modeled by a transfer graph, where vertices represent the storage devi...
详细信息
ISBN:
(纸本)3540380442
the data migration problem is to compute an efficient plan for moving data stored on devices in a network from one configuration to another. It is modeled by a transfer graph, where vertices represent the storage devices, and the edges represent the data transfers required between pairs of devices. Each vertex has a non-negative weight, and each edge has unit processing time. A vertex completes when all the edges incident on it complete;the constraint is that two edges incident on the same vertex cannot be processed simultaneously. the objective is to minimize the sum of weighted completion times of all vertices. Kim (Journal of algorithms, 55:42-57, 2005) gave an LP-rounding 3-approximation algorithm. We give a more efficient primal-dual algorithm that achieves the same approximation guarantee, which can be extended to yield a 5.83-approximation for arbitrary processing times. We also study a variant of the open shop scheduling problem. this is a special case of the data migration problem in which the transfer graph is bipartite and the objective is to minimize the completion times of edges. We present a simple algorithm that achieves an approximation ratio of root 2 approximate to 1.414, thus improving the 1.796-approximation given by Gandhi et al.(ACM Transaction on algorithms, 2(1):116-129, 2006). We show that the analysis of our algorithm is almost tight.
the proceedings contain 38 papers. the topics discussed include: top-down analysis of path compression: deriving the inverse-Ackermann bound naturally (and easily);results and problems on self-adjusting search trees a...
详细信息
ISBN:
(纸本)354035753X
the proceedings contain 38 papers. the topics discussed include: top-down analysis of path compression: deriving the inverse-Ackermann bound naturally (and easily);results and problems on self-adjusting search trees and related datastructures;multiplexing packets with arbitrary deadlines in bounded buffers;variable sized online interval coloring with bandwidth;a simpler linear-time recognition of circular-arc graphs;dynamic matching markets and voting paths;sorting by merging or merging by sorting?;finding the position of the k-mismatch and approximate tandem repeats;exponential time algorithms for the minimum dominating set problem on some graph classes;exact computation of maximum induced forest;on the approximation hardness of some generalizations of TSP;reoptimization of minimum and maximum traveling salesman's tours;and the node-weighted Steiner problem in graphs of restricted node weights.
Scalable data distribution in large-scale dynamic collaborative siwtems requires efficient, low overhead communication control. We propose here efficient algorithms fir clustering network nodes dynamically based on th...
详细信息
ISBN:
(纸本)0769526977
Scalable data distribution in large-scale dynamic collaborative siwtems requires efficient, low overhead communication control. We propose here efficient algorithms fir clustering network nodes dynamically based on their communication interest. Several group communication architecture have been proposed to date without considering the constraints imposed by the communicution infrastructure. Among these, distributed hash tables are scalable and resilient datastructures used for data dissemination control. However DHTs are not optimized for high dynamics of network node interest and real-time end-to-end performance requirements. this paper proposes efficient control algorithms for large-scale collaborative systems optimized for scalability as well as end-to-end data dissemination. Network node communication interest is modeled as a multi-dimensional attribute space partitioned into interest cells mapped to multicast communication groups. the proposed control algorithms use proximity based clustering of network nodes and hierarchical communication interest aggregation. We show that network overlay control algorithms achieve scalability and low, overhead with a controlled degradation of end-to-end data path performance.
Business Process Management (BPM) has been recognized to be important for Business Processes (BP) and enterprise information systems to continuously bring their benefits. Understanding actual BP models is a key step i...
详细信息
ISBN:
(纸本)076952558X
Business Process Management (BPM) has been recognized to be important for Business Processes (BP) and enterprise information systems to continuously bring their benefits. Understanding actual BP models is a key step in BPM because predefined models are different from actual ones, which analysis and decision-making should stand on. However, it depends on costly interviews anal observations. In this paper, we propose a method of estimating actual BP model structures from execution logs in information systems for effortless BPM. this method can utilize practical execution logs and appropriately estimate structures compared with previously proposed methods. It can also reveal how each work order was transacted and routed so that exceptional situations can be investigated in detail. We apply it to a synthetic execution log and a real-world execution log, then demonstrate its validity in terms of algorithms and its usefulness in BPM. Our method makes it possible to attain continuous BPM.
In this paper, the experimentally measured data of two sensor systems (i.e., a surface-bonded piezoelectric sensor system and a non-contact scanning laser vibrometer (SLV) system) are studied, and three dynamics-based...
详细信息
ISBN:
(纸本)0784408300
In this paper, the experimentally measured data of two sensor systems (i.e., a surface-bonded piezoelectric sensor system and a non-contact scanning laser vibrometer (SLV) system) are studied, and three dynamics-based damage detection algorithms are evaluated. the curvature mode shapes are selected as a parameter to locate damage due to its sensitivity. the piezoelectric sensors directly acquire the curvature mode shapes of the structures, while the SLV measures the displacement mode shapes. the beam specimens are made of E-glass/epoxy composites, and several different types of damages are introduced in the beams (i.e., delaminations, impact and saw cut damage). this study provides a thorough assessment of the two sensor systems to damage detection of laminated composite beams and verify the validity of dynamics-based damage detection methodology for locating the local defects in composite structures. Copyright ASCE 2006.
Path compression is used in a number of algorithms, most notably in various very natural solutions to the so-called Union-Find problem. this problem is basic and important enough to be covered in most introductory cou...
详细信息
this publication focuses on a modular architecture for sensor data fusion regarding to research work of common interest related to sensors and sensor data fusion. this architecture will be based on an extended environ...
详细信息
ISBN:
(纸本)3540334092
this publication focuses on a modular architecture for sensor data fusion regarding to research work of common interest related to sensors and sensor data fusion. this architecture will be based on an extended environment model and representation, consisting of a set of common datastructures for sensor, object and situation refinement data and algorithms as well as the corresponding models. the aim of such research is to contribute to a measurable enhancement of the output performance provided by multi-sensor systems in terms of actual availability, reliability, accuracy and precision of the perception results. In this connection, investigations towards fusion concepts and paradigms, such as 'redundant' and 'complementary', as well as 'early' and track-based sensor data fusion approaches, are conducted, in order to significantly enhance the overall performance of the perception system.
Accurate prediction of protein structures is very important for many applications such as drug discovery and biotechnology. Building side chains is an essential to get any reliable prediction of the protein structure ...
详细信息
A novel algorithm for unsupervised classification of datasets made up of integer valued patterns by means of cellular neural network (CNN) is proposed. the algorithm is suited both for linearly separable and nonlinear...
详细信息
A novel algorithm for unsupervised classification of datasets made up of integer valued patterns by means of cellular neural network (CNN) is proposed. the algorithm is suited both for linearly separable and nonlinearly separable data sets. the adopted CNN is n-dimensional and is based on a space-variant template - neighborhood order 1 - to cluster n-dimensional datasets. the choice of a CNN architecture allows a straightforward hardware implementation, particularly suited for bi-dimensional patterns
this paper presents color processing tasks of the bionic eyeglass project, which helps blind people to gather chromatic information. A color recognition method is presented, which specifies the colors of the objects o...
详细信息
this paper presents color processing tasks of the bionic eyeglass project, which helps blind people to gather chromatic information. A color recognition method is presented, which specifies the colors of the objects on the scene. the method adapts to varying illumination and smooth shadow on the objects. It performs local adaptation on the intensity and global chromatic adaptation. Another method is also shown that improves the extraction of display data based on chromatic information
暂无评论