In this paper, we derive a time-complexity bound for the gradient projection method for optimal routing in data networks. This result shows that the gradient projection algorithm of the Goldstein-Levitin-Poljak type f...
详细信息
In this paper, we derive a time-complexity bound for the gradient projection method for optimal routing in data networks. This result shows that the gradient projection algorithm of the Goldstein-Levitin-Poljak type formulated by Bertsekas converges to within epsilon in relative accuracy in O(epsilon(-2)h(min)N(max)) number of iterations, where N-max is the number of paths sharing the maximally shared link, and h(min) is the diameter of the network. Based on this complexity result, we also show that the one-source-at-a-time update policy has a complexity bound which is O(n) times smaller than that of the all-at-a-time update policy, where n is the number of nodes in the network. The result of this paper argues for constructing networks with low diameter for the purpose of reducing complexity of the network control algorithms. The result also implies that parallelizing the optimal routing algorithm over the network nodes is beneficial.
This paper presents a self-stabilizing algorithm for the minimum-depth search (MDS) of a connected undirected graph on an asynchronous distributed or network model of computation. The algorithm produces a minimum-dept...
详细信息
This paper presents a self-stabilizing algorithm for the minimum-depth search (MDS) of a connected undirected graph on an asynchronous distributed or network model of computation. The algorithm produces a minimum-depth spanning tree (MDST) of the given graph in a distributed manner so that each node of the graph knows its depth and parent. The algorithm is resilient to transient faults and does not require initialization. It has been proved that the algorithm is correct and requires O(n(2)) time, where n is the number of nodes of the graph. (C) 1999 Elsevier Science Inc. All rights reserved.
Third generation mobile radio systems will employ TD-CDMA in their TDD mode. In a TD-CDMA mobile radio system, joint-detection is equivalent to solving a least squares problem with a system matrix that exhibits some f...
详细信息
Third generation mobile radio systems will employ TD-CDMA in their TDD mode. In a TD-CDMA mobile radio system, joint-detection is equivalent to solving a least squares problem with a system matrix that exhibits some form of block-Toeplitz structure. This structure can be successfully exploited by using variations of the Schur algorithm for computing the QR decomposition of this system matrix. Together with a displacement representation, the Schur algorithm can be straightforwardly adapted to a wide variety of matrix structures. In this paper we show this approach for two concrete manifestations of the TD-CDMA system matrix: first for a very compact, block-Toeplitz structure;and second for the less favorable Toeplitz-block structure that arises when decision feedback is added to the data process.
New modifications of the Cohen-Sutherland algorithm for clipping lines and line segments in E-2 are presented. The suggested algorithms are based on a technique of coding the line direction together with the end point...
详细信息
New modifications of the Cohen-Sutherland algorithm for clipping lines and line segments in E-2 are presented. The suggested algorithms are based on a technique of coding the line direction together with the end points of the clipped line segment. They solve all cases more effectively. The algorithms are convenient for clippings lines or line segments by rectangle. Theoretical considerations and experimental results are also presented.
We study the decentralized detection problem in a general framework where arbitrary number of quantization levels at the local sensors are allowed, and transmission from the sensors to the fusion center is subject to ...
详细信息
We study the decentralized detection problem in a general framework where arbitrary number of quantization levels at the local sensors are allowed, and transmission from the sensors to the fusion center is subject to both noise and interchannel interference. We treat both Bayesian and Neyman-Pearson approaches to the problem, and develop an iterative descent algorithm to design the optimal quantizers and fusion rule. Some numerical examples for both approaches are also presented.
作者：
Popescu, DCCSIRO
Div Math & Informat Sci Canberra ACT 2601 Australia
Fractal image coding is a relatively new technique of lossy image compression which exploits the piecewise self-similarity existing in an image. in this paper we present a survey of the achievements in the field We th...
详细信息
Fractal image coding is a relatively new technique of lossy image compression which exploits the piecewise self-similarity existing in an image. in this paper we present a survey of the achievements in the field We then focus our attention on a fundamental aspect of fractal coding - that concerning the nature of the transformations used in matching natural patterns. Through the analysis of a few models we try to suggest both the difficulties and the potential of this line of research.
By the use of wavelet basis functions, an integral equation can be converted into a sparse matrix equation after discretization. Through the exploitation of the sparsity of the impedance matrix, the complexity of sort...
详细信息
We present a technique for analyzing the run time behavior of integrity constraints repair actions, i.e., active database rules specifically designed to correct violations of database integrity. When constraints becom...
详细信息
We present a technique for analyzing the run time behavior of integrity constraints repair actions, i.e., active database rules specifically designed to correct violations of database integrity. When constraints become violated due to an incorrect user transaction, rule computation is started to restore the database to a correct state. Since repair actions may be numerous and may conflict with each other, an automated support to the analysis of their run-time behavior is necessary. The proposed technique helps the rule base administrator define a repair rule selection strategy such that the computation terminates for every input transaction, the final database state satisfies all the constraints, and the user's preferences among different ways to restore integrity are taken into account. In addition, it can be used by the rule designer to spot ''dangerous'' rules that may be subject to redesign. This problem is formulated as an optimization problem on directed hypergraphs, which we demonstrate to be NP-hard and solve by means of a heuristic algorithm.
Object recognition is imperative in industry automation since it empowers robots with the perceptual capability of understanding the three-dimensional(3-D) environment by means of sensory devices. Considering object r...
详细信息
Object recognition is imperative in industry automation since it empowers robots with the perceptual capability of understanding the three-dimensional(3-D) environment by means of sensory devices. Considering object recognition as a mapping between object models and a partial description of an object, this paper introduces a three-phase filtering method that eliminates candidate models when their differences with the object show up. Throughout the process, a view-insensitive modeling method, namely localized surface parameters, is employed. Surface matching is carried out in the first phase to match models with the object by comparing their localized surface descriptions. A model is a candidate of the object only if every object surface matches locally with at least one of the model surfaces. Since the topological relationship between surfaces specifies the global shape of the object and models, it is then checked in the next phase with local coordinate systems to make sure that a candidate model has the identical structure as the object. Because the information of an object cannot be complete in a single viewing direction, the first two conditions can only determine if a candidate has the same portion as the object. The selected model may still be bigger than the object. To avoid the part-to-whole confusion, in the third phase, a back projection from candidate models is performed to ensure that no unmatched model features become visible when a model is virtually brought to the object's orientation. In case multiple models are selected as a result of the insufficient information, disambiguating features and their visible directions are derived to verify the expected feature. In addition to the view independent object recognition under even ambiguous situations, the filtering method has a low computational complexity upper bounded by O (m(2)n(2)) and lower bounded by O(mn), where m and n are the numbers of model and object features. The three-phase object recognition
By the use of wavelet basis functions, an integral equation can be converted into a sparse matrix equation after discretization. Through the exploitation of the sparsity of the impedance matrix;the complexity of solvi...
详细信息
By the use of wavelet basis functions, an integral equation can be converted into a sparse matrix equation after discretization. Through the exploitation of the sparsity of the impedance matrix;the complexity of solving the resultant matrix equation can be greatly reduced. It has beet reported that the number of nonzero elements in a wavelet impedance matrix is alpha N-2 (0 less than or equal to alpha less than or equal to 1), where a is approximately a constant. This implies that solving the sparse matrix equation produced by a wavelet expansion has the same complexity as solving a full matrix In this Letter, however, we present an example of the wavelet impedance matrix that results in a much lower complexity-O(N). (C) 1997 John Wiley & Sons, Inc.
暂无评论