检索结果-内蒙古大学图书馆

Efficiently pricing European-Asian options - ultimate implementation and analysis of the AMO algorithm

INFORMATION PROCESSING LETTERS 2006年第6期100卷 213-219页

作者： Shioura, Akiyoshi Tokuyama, Takeshi Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan

Options are popular and important financial instruments in world financial markets. One of the simplest options is European call option, which is a contract giving its holder the right, but not the obligation, to buy a stock or other financial asset at some point in the future (called the expiration date) for a specified price X (called the strike price). The payoff of an option is the amount of money its holder makes on the contract. Suppose that we have a European option on a stock, and the stock price S is more than the strike price X on the expiration date. Then, we can make some money by exercising the option to buy the stock and selling the stock immediately at the market price. Hence, the payoff of a European option is given by (S — X)~+ = max{S — X, 0}. The price of the option is usually much less than the actual price of the underlying stock. Therefore, options hedge risk more cheaply than stocks only, and provide a chance to get large profit with a small amount of money if one's speculation is good.

关键词： analysis of algorithms approximation algorithms European-Asian option option pricing randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

A stopping rule for stochastic approximation

引用

AUTOMATICA 2015年 60卷 1-6页

作者： Wada, Takayuki Fujisaki, Yasumasa Osaka Univ Dept Informat & Phys Sci Suita Osaka 5650871 Japan

A stochastic approximation algorithm is a recursive procedure to find the solution to an unknown nonlinear equation via noisy measurements. In this paper, we present a stopping rule for a stochastic approximation. We show that there is a high probability that the distance between the exact solution and the candidate solution is less than a specified tolerance level when the stochastic approximation stops according to our stopping rule. Furthermore, the number of recursions required by the stopping rule is a polynomial function of the problem size. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： Stochastic approximation randomized algorithms Adaptive control System identification

来源：评论

学校读者我要写书评

暂无评论

Performance Analysis of M2M Data Collection Networks Using Dynamic Frame-Slotted ALOHA

IEEE TRANSACTIONS ON GREEN COMMUNICATIONS AND NETWORKING

引用

IEEE TRANSACTIONS ON GREEN COMMUNICATIONS AND NETWORKING 2018年第2期2卷 493-505页

作者： George, Arun Venkatesh, T. G. Indian Inst Technol Madras Dept Elect Engn Chennai 600036 Tamil Nadu India

We are witnessing an explosion in the growth of the number of connected devices, with the consequent increase of their share in global energy consumption. Thus, it is mandatory that we employ green networking technologies for Internet of Things and machine to machine (M2M) networks. In M2M data collection networks, hundreds or thousands of devices communicate with a data collector (DC). In this regard, dynamic frame slotted Aloha (DFSA) has gained popularity as an energy efficient MAC protocol for M2M data collection networks. In this paper, we carry out performance evaluation of DFSA algorithm. First, we derive analytical bounds on the performance of DFSA. To this end, we employ the properties of binomial distributions and Karp-Upfal-Widgerson inequality. Furthermore, we propose a simple MAC protocol based on DFSA, and analyze the protocol under saturated traffic condition. Using a mathematical model for our proposed protocol, we derive closed form expressions for system throughput, packet delay, and the energy efficiency of the node and the DC. The analysis is validated through extensive simulation.

关键词： Dynamic frame slotted ALOHA M2M sensor networks randomized algorithms Karp-Upfal-Widgerson inequalities

来源：评论

学校读者我要写书评

暂无评论

Fast distributed algorithm for convergecast in ad hoc geometric radio networks

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2006年第4期66卷 578-585页

作者： Kesselman, A Kowalski, DR Max Planck Inst Informat Saarbrucken Germany Univ Liverpool Dept Comp Sci Liverpool L69 3BX Merseyside England

Wireless ad hoc radio networks have gained a lot of attention in recent years. We consider geometric networks, where nodes are located in a Euclidean plane. We assume that each node has a variable transmission range and can learn the distance to the closest active neighbor at any time. We also assume that nodes have a special collision detection (CD) capability so that a transmitting node can detect a collision within its transmission range. We study the basic communication problem of collecting data from all nodes called convergecast. Recently, there appeared many new applications such as real-time multimedia, battlefield communications and rescue operations that impose stringent delay requirements on the convergecast time. We measure the latency of convergecast, that is the number of time steps needed to collect the data in any n-node network. We propose a very simple randomized distributed algorithm that has the expected running time O(log n). We also show that this bound is tight and any algorithm needs Omega(log n) time steps while performing convergecast in an arbitrary network. One of the most important problems in wireless ad hoc networks is to minimize the energy consumption, which maximizes the network lifetime. We study the trade-off between the energy and the latency of convergecast. We show that our algorithm consumes at most O(n log n) times the minimum energy. We also demonstrate that for a line topology, the minimum energy convergecast takes n time steps while any algorithm performing convergecast within O(log n) time steps requires Omega(n/log n) times the minimum energy. (c) 2006 Elsevier Inc. All rights reserved.

关键词： radio networks convergecast randomized algorithms energy/latency trade-off

来源：评论

学校读者我要写书评

暂无评论

Simple on-line algorithms for the maximum disjoint paths problem

引用

ALGORITHMICA 2004年第3期39卷 209-233页

作者： Kolman, P Scheideler, C Charles Univ Prague Inst Theoret Comp Sci CR-11800 Prague Czech Republic Johns Hopkins Univ Dept Comp Sci Baltimore MD 21218 USA

In this paper we study the classical problem of finding disjoint paths in graphs. This problem has been studied by a number of authors both for specific graphs and general classes of graphs. Whereas for specific graphs many (almost) matching upper and lower bounds are known for the competitiveness of on-line algorithms, not much is known about how well on-line algorithms can perform in the general setting. The best results obtained so far use the expansion of a network to measure the algorithm's performance. We use a different parameter called the routing number that, as we will show, allows more precise results than the expansion. It enables us to prove tight upper and lower bounds for deterministic on-line algorithms. The upper bound is obtained by surprisingly simple greedy-like algorithms. Interestingly, our upper bound on the competitive ratio is even better than the best previous approximation ratio for off-line algorithms. Furthermore, we introduce a refined variant of the routing number and show that this variant allows us, for some classes of graphs, to construct on-line algorithms with a competitive ratio significantly below the best possible upper bound that could be obtained using the routing number or the expansion of a network only. We also show that our on-line algorithms can be transformed into efficient algorithms for the more general unsplittable flow problem.

关键词： disjoint paths problem approximation greedy algorithms randomized algorithms unsplittable flow

来源：评论

学校读者我要写书评

暂无评论

Efficient and scalable algorithms for inferring likely invariants in distributed systems

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2007年第11期19卷 1508-1523页

作者： Jiang, Guofei Chen, Haifeng Yoshihira, Kenji NEC Labs Amer Inc Princeton NJ 08540 USA

Distributed systems generate a large amount of monitoring data such as log files to track their operational status. However, it is hard to correlate such monitoring data effectively across distributed systems and along observation time for system management. In previous work, we proposed a concept named flow intensity to measure the intensity with which internal monitoring data reacts to the volume of user requests. We calculated flow intensity measurements from monitoring data and proposed an algorithm to automatically search constant relationships between flow intensities measured at various points across distributed systems. If such relationships hold all the time, we regard them as invariants of the underlying systems. Invariants can be used to characterize complex systems and support various system management tasks. However, the computational complexity of the previous invariant search algorithm is high so that it may not scale well in large systems with thousands of measurements. In this paper, we propose two efficient but approximate algorithms for inferring invariants in large-scale systems. The computational complexity of new randomized algorithms is significantly reduced, and experimental results from a real system are also included to demonstrate the accuracy and efficiency of our new algorithms.

关键词： distributed systems monitoring data time series data management invariants randomized algorithms computational complexity

来源：评论

学校读者我要写书评

暂无评论

Fully Connected Networks on a Diet With the Mediterranean Matrix Multiplication

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 2024年第1期35卷 634-647页

作者： Eshkiki, Hassan Mora, Benjamin Xie, Xianghua Swansea Univ Dept Comp Sci Computat Foundry Swansea SA1 8EN W Glam Wales

This article proposes the Mediterranean matrix multiplication, a new, simple and practical randomized algorithm that samples angles between the rows and columns of two matrices with sizes m, n, and p to approximate matrix multiplication in O(k(mn+np+mp)) steps, where k is a constant only related to the precision desired. The number of instructions carried out is mainly bounded by bitwise operators, amenable to a simplified processing architecture and compressed matrix weights. Results show that the method is superior in size and number of operations to the standard approximation with signed matrices. Equally important, this article demonstrates a first application to machine learning inference by showing that weights of fully connected layers can be compressed between 30x and 100x with little to no loss in inference accuracy. The requirements for pure floating-point operations are also down as our algorithm relies mainly on simpler bitwise operators.

关键词： Matrix multiplication neural networks randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Sensor networks: From dependence analysis via matroid bases to online synthesis

引用

THEORETICAL COMPUTER SCIENCE 2014年第0期553卷 2-17页

作者： Cohen, Asaf Dolev, Shlomi Leshem, Guy Ben Gurion Univ Negev Dept Commun Syst Engn IL-84105 Beer Sheva Israel Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel Ashkelon Acad Coll Dept Comp Sci Ashqelon Israel

Consider the two related problems of sensor selection and sensor fusion. In the first, given a set of sensors, one wishes to identify a subset of the sensors, which while small in size, captures the essence of the data gathered by the sensors. In the second, one wishes to construct a fused sensor, which utilizes the data from the sensors (possibly after discarding dependent ones) in order to create a single sensor which is more reliable than each of the individual ones. In this work, we rigorously define the dependence among sensors in terms of joint empirical measures and incremental parsing. We show that these measures adhere to a polymatroid structure, which in turn facilitates the application of efficient algorithms for sensor selection. We suggest both a random and a greedy algorithm for sensor selection. Given an independent set, we then turn to the fusion problem, and suggest a novel variant of the exponential weighting algorithm. In the suggested algorithm, one competes against an augmented set of sensors, which allows it to converge to the best fused sensor in a family of sensors, without having any prior data on the sensors' performance. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Sensor networks Dependence analysis Polymatroids Matroid optimization randomized algorithms Greedy selection Empirical measures Lempel-Ziv Incremental parsing Online fusion

来源：评论

学校读者我要写书评

暂无评论

Auto-configuration of Physical Cell ID in LTE femtocellular systems using Self Organizing Networks

引用

WIRELESS NETWORKS 2014年第5期20卷 1107-1120页

作者： Saxena, Navrati Roy, Abhishek Kim, HanSeok Won, Jeong-Jae Sungkyunkwan Univ Suwon South Korea Samsung Elect Syst Design Lab Suwon South Korea

The commercial success of cellular networks, combined with advances in digital electronics, signal processing, and telecommunications research have lead to the design of next generation 4G-based long term evolution (LTE) wireless systems. The key essence of these emerging, LTE cellular systems lie in deployment of multiple femtocells for improved coverage and higher data rates. However, the arbitrary deployment of a wide number of femtocells makes the configuration, management and planning of LTE systems quite complex and challenging. In order to support dynamic and efficient network configuration, every cell needs to be assigned a particular Physical Cell ID (PCID). In this paper we show that the dynamic, optimal PCID allocation problem in LTE systems is NP-complete. Subsequently we provide a near-optimal solution using Self-Organizing Networks which models the problem using new merge operations and explores the search space using a suitable randomized algorithmic approach. We also discuss two feasible options for dynamic auto-configuration of the system and analyze the algorithm to prove its convergence. Simulation results point out that our proposed near-optimal solution dynamically achieves similar to 85-90 % of global optimal auto-configuration in computationally feasible time.

关键词： LTE SON Vertex coloring NP-complete Permutation randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

The distribution of values in the quadratic assignment problem

引用

MATHEMATICS OF OPERATIONS RESEARCH 2003年第1期28卷 64-91页

作者： Barvinok, A Stephen, T Univ Michigan Dept Math Ann Arbor MI 48109 USA Univ Minnesota Inst Math & Its Applicat IMA Minneapolis MN 55455 USA

We obtain a number of results regarding the distribution of values of a quadratic function f on the set of n x n permutation matrices (identified with the symmetric group S) around its optimum,. (minimum or maximum). We estimate the fraction of permutations sigma such that f (sigma) lies within a given neighborhood of the optimal value of f and relate the optimal value with the average value of f over a neighborhood of the optimal permutation. We describe a natural class of functions (which includes, for example, the objective function in the Traveling Salesman Problem) with a relative abundance of near-optimal permutations. Also, we identify a large class of functions f with the property that permutations close to the optimal permutation in the Hamming metric of S-n tend to produce near optimal values of f (such is, for example, the objective function in the symmetric Traveling Salesman Problem). We show that for general f, just the opposite behavior may take place: an average permutation in the vicinity of the optimal permutation may be much worse than an average permutation in the whole group S-n.

关键词： Quadratic Assignment Problem distribution symmetric group randomized algorithms heuristics representation theory

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：