In this paper, we consider a popular randomized broadcasting algorithm called push-algorithm defined as follows. Initially, one vertex of a graph G = (V, E) owns a piece of information which is spread iteratively to a...
详细信息
In this paper, we consider a popular randomized broadcasting algorithm called push-algorithm defined as follows. Initially, one vertex of a graph G = (V, E) owns a piece of information which is spread iteratively to all other vertices: in each timestep t = 1, 2, ... every informed vertex chooses a neighbor uniformly at random and informs it. The question is how many time steps are required until all vertices become informed (with high probability). For various graph classes, involved methods have been developed in order to show an upper bound of O(log N + diam(G)) on the runtime of the push-algorithm, where N is the number of vertices and diam(G) denotes the diameter of G. However, no asymptotically tight bound on the runtime based on the mixing time of random walks has been established. In this work we fill this gap by deriving an upper bound of O(T-mix+ logN), where T-mix denotes the mixing time of a certain random walk on G. After that we prove upper bounds that are based on certain edge expansion properties of G. However, for hypercubes neither the bound based on the mixing time nor the bounds based on edge expansion properties are tight. That is why we develop a general way to combine these two approaches by which we can deduce that the runtime of the push-algorithm is Theta (logN) on every Hamming graph.
In dealing with abrasive waterjet machining（AWJM） simulation,most literatures apply finite element method（FEM） to build pure waterjet models or single abrasive particle erosion *** overcome the mesh distortion cau...
详细信息
In dealing with abrasive waterjet machining（AWJM） simulation,most literatures apply finite element method（FEM） to build pure waterjet models or single abrasive particle erosion *** overcome the mesh distortion caused by large deformation using FEM and to consider the effects of both water and abrasive,the smoothed particle hydrodynamics（SPH） coupled FEM modeling for AWJM simulation is presented,in which the abrasive waterjet is modeled by SPH particles and the target material is modeled by *** two parts interact through contact *** this model,abrasive waterjet with high velocity penetrating the target materials is simulated and the mechanism of erosion is *** relationships between the depth of penetration and jet parameters,including water pressure and traverse speed,etc,are analyzed based on the *** simulation results agree well with the existed experimental *** mixing multi-materials SPH particles,which contain abrasive and water,are adopted by means of the randomized algorithm and material model for the abrasive is *** study will not only provide a new powerful tool for the simulation of abrasive waterjet machining,but also be beneficial to understand its cutting mechanism and optimize the operating parameters.
An axis-parallel k-dimensional box is a Cartesian product R-1 x R-2 x...x R-k where R-i (for 1 = 1 when d >= 2. In most cases, the first step usually is computing a low dimensional box representation of the given g...
详细信息
An axis-parallel k-dimensional box is a Cartesian product R-1 x R-2 x...x R-k where R-i (for 1 <= i <= k) is a closed interval of the form [a(i), b(i)] on the real line. For a graph G, its boxicity box(G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a left perpendicular1 + 1/c log n right perpendicular(d-1) approximation ratio for any constant c >= 1 when d >= 2. In most cases, the first step usually is computing a low dimensional box representation of the given graph. Deciding whether the boxicity of a graph is at most 2 itself is NP-hard. We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in left perpendicular(Delta + 2) ln nright perpendicular dimensions, where Delta is the maximum degree of G. This algorithm implies that box(G) <= left perpendicular(Delta + 2) ln nright perpendicular for any graph G. Our bound is tight up to a factor of ln n. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree Delta, we show that for almost all graphs on n vertices, their boxicity is O(d(av) ln n) where d(av) is the average degree.
We present a simple randomized algorithmic framework for connected facility location problems. The basic idea is as follows: We run a black-box approximation algorithm for the unconnected facility location problem, ra...
详细信息
We present a simple randomized algorithmic framework for connected facility location problems. The basic idea is as follows: We run a black-box approximation algorithm for the unconnected facility location problem, randomly sample the clients, and open the facilities serving sampled clients in the approximate solution. Via a novel analytical tool, which we term core detouring, we show that this approach significantly improves over the previously best known approximation ratios for several NP-hard network design problems. For example, we reduce the approximation ratio for the connected facility location problem from 8.55 to 4.00 and for the single-sink rent-or-buy problem from 3.55 to 2.92. The mentioned results can be derandomized at the expense of a slightly worse approximation ratio. The versatility of our framework is demonstrated by devising improved approximation algorithms also for other related problems. (C) 2010 Elsevier Inc. All rights reserved.
Abrasive waterjet machining (AWJM) is a non-conventional process. The mechanism of material removing in AWJM for ductile materials and existing erosion models are reviewed in this paper. To overcome the difficulties o...
详细信息
Abrasive waterjet machining (AWJM) is a non-conventional process. The mechanism of material removing in AWJM for ductile materials and existing erosion models are reviewed in this paper. To overcome the difficulties of fluid-solid interaction and extra-large deformation problem using finite element method (FEM), the SPH-coupled FEM modeling for abrasive waterjet machining simulation is presented, in which the abrasive waterjet is modeled by SPH particles and the target material is modeled by FE. The two parts interact through contact algorithm. The creativity of this model is multi-materials SPH particles, which contain abrasive and water and mix together uniformly. To build the model, a randomized algorithm is proposed. The material model for the abrasive is first presented. Utilizing this model, abrasive waterjet penetrating the target materials with high velocity is simulated and the mechanism of erosion is depicted. The relationship between the depth of penetration and jet parameters, including water pressure and traverse speed, etc., are analyzed based on the simulation. The results agree with the experimental data well. It will be a benefit to understand the abrasive waterjet cutting mechanism and optimize the operating parameters.
The Fisher scoring method is widely used for likelihood maximization, but its application can be difficult in situations where the expected information matrix is not available in closed form or when parameters have co...
详细信息
The Fisher scoring method is widely used for likelihood maximization, but its application can be difficult in situations where the expected information matrix is not available in closed form or when parameters have constraints In this paper, we describe an interpolation family that generalizes the Fisher scoring method and propose a general Monte Carlo approach that makes these generalized methods also applicable in such situations. With this approach, random samples are generated from the iteratively estimated models and used to provide estimates of the expected information As a result, the likelihood function can be optimized by repeatedly solving weighted linear regression problems Specific extensions of this general approach to fitting multivariate normal mixtures and to fitting mixed-effects models with a single discrete random effect are also described. Numerical studies show that the proposed algorithms are fast and reliable to use, as compared with the classical expectation-maximization algorithm (C) 2010 Elsevier B V All rights reserved
Ultrasound guidance is used for many surgical interventions such as biopsy and electrode insertion. We present a method to localize a thin surgical tool such as a biopsy needle or a microelectrode in a 3-D ultrasound ...
详细信息
Ultrasound guidance is used for many surgical interventions such as biopsy and electrode insertion. We present a method to localize a thin surgical tool such as a biopsy needle or a microelectrode in a 3-D ultrasound image. The proposed method starts with thresholding and model fitting using random sample consensus for robust localization of the axis. Subsequent local optimization refines its position. Two different tool image models are presented: one is simple and fast and the second uses learned a priori information about the tool's voxel intensities and the background. Finally, the tip of the tool is localized by finding an intensity drop along the axis. The simulation study shows that our algorithm can localize the tool at nearly real-time speed, even using a MATLAB implementation, with accuracy better than 1 mm. In an experimental comparison with several alternative localization methods, our method appears to be the fastest and the most robust one. We also show the results on real 3-D ultrasound data from a PVA cryogel phantom, turkey breast, and breast biopsy.
In this paper, we survey online algorithms in computational geometry that have been designed for mobile robots for searching a target and for exploring a region in the plane. (C) 2010 Elsevier Inc. All rights reserved.
In this paper, we survey online algorithms in computational geometry that have been designed for mobile robots for searching a target and for exploring a region in the plane. (C) 2010 Elsevier Inc. All rights reserved.
Recently, Byrka, Grandoni, RothvoBand Sanita gave a 1.39 approximation for the Steiner tree problem, using a hypergraph-based linear programming relaxation. They also upper-bounded its integrality gap by 1.55. We desc...
详细信息
Recently, Byrka, Grandoni, RothvoBand Sanita gave a 1.39 approximation for the Steiner tree problem, using a hypergraph-based linear programming relaxation. They also upper-bounded its integrality gap by 1.55. We describe a shorter proof of the same integrality gap bound, by applying some of their techniques to a randomized loss-contracting algorithm. (C) 2010 Elsevier B.V. All rights reserved.
We study the problem of computing the similarity between two piecewise-linear bivariate functions defined over a common domain, where the surfaces they define in 3D-polyhedral terrains-can be transformed vertically by...
详细信息
ISBN:
(纸本)9781450300162
We study the problem of computing the similarity between two piecewise-linear bivariate functions defined over a common domain, where the surfaces they define in 3D-polyhedral terrains-can be transformed vertically by a linear transformation of the third coordinate (scaling and translation). We present a randomized algorithm that minimizes the maximum vertical distance between the graphs of the two functions, over all linear transformations of one of the terrains, in O(n(4/3) polylog n) expected time, where n is the total number of vertices in the graphs of the two functions. We also study the computation of similarity between two univariate or bivariate functions by minimizing the area or volume between their graphs. For univariate functions we give a (1 + epsilon)-approximation algorithm for minimizing the area that runs in O(n/root epsilon) time, for any fixed epsilon > 0. The (1 + epsilon)-approximation algorithm for the bivariate version, where volume is minimized, runs in O(n/epsilon(2)) time, for any fixed epsilon > 0, provided the two functions are defined over the same triangulation of their domain.
暂无评论