We consider Kleinberg's celebrated small world graph model [12, 13], in which a D-dimensional grid {0,...,n - 1}1) is augmented with a constant number of additional unidirectional edges leaving each node. These lo...
详细信息
ISBN:
(纸本)9781611973389
We consider Kleinberg's celebrated small world graph model [12, 13], in which a D-dimensional grid {0,...,n - 1}1) is augmented with a constant number of additional unidirectional edges leaving each node. These long range edges are determined at random according to a probability distribution (the augmenting distribution), which is the same for each node. Kleinberg suggested using the inverse D-th power distribution, in which node v is the long range contact of node u with a probability proportional to ||u - v|| 1-D. He showed that such an augmenting distribution allows to route a message efficiently in the resulting random graph: The greedy algorithm, where in each intermediate node the message travels over a link that brings the message closest to the target w.r.t. the Manhattan distance, finds a path of expected length O((logn)2) between any two nodes. In this paper we prove that greedy routing does not perform asymptotically better for any uniform and isotropic augmenting distribution, i.e., the probability that node u has a particular long range contact v is independent of the labels of u and v and only a function of ||u - v||1,. In particular, we show that for such graphs the expected greedy routing time between two arbitrary nodes s and t is Ω((log||s - T||1)2). This lower bound proves and strengthens a conjecture by Aspnes, Diamadi, and Shah [1]. In order to obtain the result, we introduce a novel proof technique: We define a so-called budget game, in which a token travels over a game board, from one end to the other, while the player manages a "probability budget". In each round, the player "bets" part of her remaining probability budget on step sizes. A step size is chosen at random according to a probability distribution of the player's bet. The token then makes progress as determined by the chosen step size, while some of the player's bet is removed from her probability budget. We prove a tight lower bound for such a budget game, and then obtain a lower b
The Hepatocellular Carcinoma (HCC) is the most often met malignant tumor of the liver. It develops from cirrhosis, after a parenchyma restructuring phase, at the end of which dysplastic nodules result that can transfo...
详细信息
Software requirements modeling (SRM) is a subprocess of requirements engineering (RE) which is used to elicit and represent the need of the stakeholders. Different systematic literature reviews (SLR) have been perform...
详细信息
We consider a multi-receivers Bayesian persuasion model where an informed sender tries to persuade a group of receivers to take a certain action. The state of nature is known to the sender, but it is unknown to the re...
详细信息
ISBN:
(纸本)9783959770293
We consider a multi-receivers Bayesian persuasion model where an informed sender tries to persuade a group of receivers to take a certain action. The state of nature is known to the sender, but it is unknown to the receivers. The sender is allowed to commit to a signaling policy where she sends a private signal to every receiver. This work studies the computation aspects of finding a signaling policy that maximizes the sender's revenue. We show that if the sender's utility is a submodular function of the set of receivers that take the desired action, then we can efficiently find a signaling policy whose revenue is at least (1 - 1/e) times the optimal. We also prove that approximating the sender's optimal revenue by a factor better than (1 - 1/e) is NP-hard and, hence, the developed approximation guarantee is essentially tight. When the sender's utility is a function of the number of receivers that take the desired action (i.e., the utility function is anonymous), we show that an optimal signaling policy can be computed in polynomial time. Our results are based on an interesting connection between the Bayesian persuasion problem and the evaluation of the concave closure of a set function.
This paper proposes a universal method for improving the dynamic characteristics of induction motors. The transient processes here fluctuate greatly, which reduces the energy efficiency of the electromechanical conver...
详细信息
This paper propose a method for identification of complex engineering systems using wavelet transform. This transform is chosen because it can provide a well localization both in time and in frequency. The method is a...
详细信息
In ensemble learning, several base learners are combined together in some way to get a stronger learner. Good ensembles are often much more accurate than individual learners that make them up. Ensemble pruning searche...
详细信息
In this paper, we address the control problem of an uncertain robotic manipulator with input saturations, unknown input scalings and disturbances. For this purpose, a model reference adaptive control like (MRAC-like...
详细信息
In this paper, we address the control problem of an uncertain robotic manipulator with input saturations, unknown input scalings and disturbances. For this purpose, a model reference adaptive control like (MRAC-like) is used to handle the input saturations. The model reference is input to state stable (ISS) and driven by the errors between the required control signals and input saturations. The uncertain parameters are dealt with by using linear-in-the-parameters property of robotic dynamics, while unknown input scalings and disturbances are handled by non-regressor based approach. Our design ensures that all the signals in the closed-loop system are bounded, and the tracking error converges to the compact set which depends on the predetermined bounds of the control inputs. Simulation on a planar elbow manipulator with two joints is provided to illustrate the effectiveness of the proposed controller.
This paper describes the results of a study undertaken on Master of science students in order to analyse their characteristics as digital students and how this can influence their use of the "Politehnica" Un...
详细信息
The aim of this paper is to dress up a guideline to choose a suitable forecasting technique with fuzzy logic support. First of all, the smart grids, framework for low-voltage networks with distributed energy from rene...
详细信息
暂无评论