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

6th International Conference on Operations Research and Enterprise Systems (ICORES)

作者： Georgiou, Konstantinos Karakostas, George Kranakis, Evangelos Ryerson Univ Dept Math 350 Victoria St Toronto ON M5B 2K3 Canada McMaster Univ Dept Comp & Software 1280 Main St West Hamilton ON L8S 4K1 Canada Carleton Univ Sch Comp Sci 1125 Col By Dr Ottawa ON K1S 5B6 Canada

ISBN: (纸本)9789897582189

We introduce and study treasure-evacuation with 2 robots, a new problem on distributed searching and fetching related to well studied problems in searching, rendezvous and exploration. The problem is motivated by real-life search-and-rescue operations in areas of a disaster, where unmanned vehicles (robots) search for a victim (treasure) and subsequently bring (fetch) her to safety (the exit). One of the critical components in such operations is the communication protocol between the robots. We provide search algorithms and contrast two standard models, the face-to-face and the wireless model. Our main technical contribution pertains to the face-to-face model. More specifically, we demonstrate how robots can take advantage of some minimal information of the topology (i.e., the disk) in order to allow for information exchange without meeting. The result is a highly efficient distributed treasure-evacuation protocol which is minimally affected by the lack of distant communication.

关键词： Search & Fetch distributed algorithm Rendevouz Exploration Face-to-Face Model Wireless Model

来源：评论

学校读者我要写书评

暂无评论

Funplace: A Protocol for Network Function Placement 42

Funplace: A Protocol for Network Function Placement

引用

IEEE 42nd Conference on Local Computer Networks (IEEE LCN)

作者： Anbiah, Anix Sivalingam, Krishna M. Indian Inst Technol Madras Dept Comp Sci & Engn Madras Tamil Nadu India

ISBN: (纸本)9781509065226

The Network Function Placement (NFP) problem involves placing Virtual Network Functions (VNFs) in a network in order to meet the Service Function Chain (SFC) requirements of the flows through the network. Simultaneously, the usage of network resources by the VNF instances must be optimized. Prior work primarily treated this as a constraint satisfaction problem, using linear programming to find optimal solutions. In contrast, this paper presents a distributed approach, based on a message-passing network protocol. This approach allows network nodes to negotiate the placement of VNF instances. A discreteevent simulation of the protocol is used to demonstrate it as a viable technique. A non-linearly constrained optimization (NCO) formulation is used to find optimal solutions for comparison and it is shown that the protocol yields nearly optimal solutions.

关键词： Network Function Placement Virtual Network Functions distributed algorithm Network Protocol

来源：评论

学校读者我要写书评

暂无评论

A Time Hierarchy Theorem for the LOCAL Model 58

A Time Hierarchy Theorem for the LOCAL Model

引用

58th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Chang, Yi-Jun Pettie, Seth Univ Michigan Ann Arbor MI 48109 USA

ISBN: (纸本)9781538634646

The celebrated Time Hierarchy Theorem for Turing machines states, informally, that more problems can be solved given more time. The extent to which a time hierarchy-type theorem holds in the classic distributed LOCAL model has been open for many years. In particular, it is consistent with previous results that all natural problems in the LOCAL model can be classified according to a small constant number of complexities, such as O(1), O(log*n), O (log n), 2O((root log n)), etc. In this paper we establish the first time hierarchy theorem for the LOCAL model and prove that several gaps exist in the LOCAL time hierarchy. Our main results are as follows: We define an infinite set of simple coloring problems called Hierarchical 21/2-Coloring. A correctly colored graph can be confirmed by simply checking the neighborhood of each vertex, so this problem fits into the class of locally checkable labeling (LCL) problems. However, the complexity of the k-level Hierarchical 21/2-Coloring problem is circle minus(n(1/k)), for k is an element of Z(+). The upper and lower bounds hold for both general graphs and trees, and for both randomized and deterministic algorithms. Consider any LCL problem on bounded degree trees. We prove an automatic-speedup theorem that states that any randomized n(o(1))-time algorithm solving the LCL can be transformed into a deterministic O (log n)-time algorithm. Together with a previous result, this establishes that on trees, there are no natural deterministic complexities in the ranges omega(log*n)-o(log n) or omega(log n)-n(o(1)). We expose a gap in the randomized time hierarchy on general graphs. Roughly speaking, any randomized algorithm that solves an LCL problem in sublogarithmic time can be sped up to run in O(T-LLL) time, which is the complexity of the distributed Lovasz local lemma problem, currently known to be Omega (log log n) and 2(O(root log log n)) on bounded degree graphs. Finally, we revisit Naor and Stockmeyer's characterization of O(1

关键词： distributed algorithm locally checkable labeling local model time hierarchy theorem

来源：评论

学校读者我要写书评

暂无评论

Equilibrium Analysis of Electricity Market with Wind Power Bidding and Demand Response Bidding

Equilibrium Analysis of Electricity Market with Wind Power B...

引用

International Conference on Life System Modeling and Simulation (LSMS) / International Conference on Intelligent Computing for Sustainable Energy and Environment (ICSEE)

作者： Zhang, Kai Wang, Xian Zhang, Shaohua Shanghai Univ Sch Mechatron Engn & Automat Key Lab Power Stn Automat Technol Shanghai Peoples R China

ISBN: (纸本)9789811063640;9789811063633

In electricity markets with strategic bidding of wind power, it is important to handle wind power's output deviation. In this paper, the scenario where customers in Demand Response (DR) program matches the wind power's output deviation through strategic bidding is studied, and a stochastic equilibrium model of the electricity market with wind power bidding and demand response bidding is proposed. In this model, linear supply function bidding is applied by both wind power producers and traditional power producers to match power demand in wholesale market. In order to compensate for the wind power's output deviation, two market models in balancing market for demand response are proposed where supply function bidding and demand function bidding are applied by DR customers to match supply deficit and surplus respectively. Furthermore, the penalty cost for output deviation of the wind power producer is determined by the equilibrium price in balancing market. The equilibrium problems are solved by being reverse-engineered into convex optimization problems and the existence and uniqueness of the Nash equilibrium is theoretically proved. A distributed dual gradient algorithm is further proposed to achieve the equilibrium. Numerical examples are presented to verify the validity of the proposed model and effectiveness of the algorithms.

关键词： Electricity market Wind power bidding Demand response bidding distributed algorithm Equilibrium analysis

来源：评论

学校读者我要写书评

暂无评论

A distributed algorithm for the Replica Placement Problem

引用

IEEE TRANSACTIONS ON PARALLEL AND distributed SYSTEMS 2011年第9期22卷 1455-1468页

作者： Zaman, Sharrukh Grosu, Daniel Wayne State Univ Dept Comp Sci Detroit MI 48202 USA

Caching and replication of popular data objects contribute significantly to the reduction of the network bandwidth usage and the overall access time to data. Our focus is to improve the efficiency of object replication within a given distributed replication group. Such a group consists of servers that dedicate certain amount of memory for replicating objects requested by their clients. The content replication problem we are solving is defined as follows: Given the request rates for the objects and the server capacities, find the replica allocation that minimizes the access time over all servers and objects. We design a distributed approximation algorithm that solves this problem and prove that it provides a 2-approximation solution. We also show that the communication and computational complexity of the algorithm is polynomial with respect to the number of servers, the number of objects, and the sum of the capacities of all servers. Finally, we perform simulation experiments to investigate the performance of our algorithm. The experiments show that our algorithm outperforms the best existing distributed algorithm that solves the replica placement problem.

关键词： Replication distributed replication group distributed algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A distributed algorithm for Resource Allocation in OFDM Cognitive Radio Systems

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2011年第2期60卷 546-554页

作者： Zhang, Yonghong Leung, Cyril Univ British Columbia Dept Elect & Comp Engn Vancouver BC V6T 1Z4 Canada

We study the problem of allocating subchannels, bits, and powers in a cognitive radio system, in which available system resources are highly dynamic. The modulation scheme employed is orthogonal frequency-division multiplexing (OFDM). In a resource-limited situation under which the nominal-rate requirements of users cannot be satisfied, it is desirable to provide fair degradation among users. In a situation with abundant resources, we may choose to maximize system throughput while ensuring that user nominal-rate requirements are met. The problem is formulated as a single objective nonlinear optimization problem using techniques from goal programming. A distributed resource allocation algorithm is proposed and shown to provide good fairness. In resource-abundant situations, the proposed distributed algorithm yields significantly better system throughput compared with the proportional-rate algorithm.

关键词： Ad hoc systems cognitive radio (CR) distributed algorithm goal programming orthogonal frequency-division multiplexing (OFDM) resource allocation

来源：评论

学校读者我要写书评

暂无评论

distributed Variational Bayesian algorithms Over Sensor Networks

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2016年第3期64卷 783-798页

作者： Hua, Junhao Li, Chunguang Zhejiang Univ Dept Informat Sci & Elect Engn Hangzhou 310027 Zhejiang Peoples R China

distributed inference/estimation in Bayesian framework in the context of sensor networks has recently received much attention due to its broad applicability. The variational Bayesian (VB) algorithm is a technique for approximating intractable integrals arising in Bayesian inference. In this paper, we propose two novel distributed VB algorithms for general Bayesian inference problem, which can be applied to a very general class of conjugate- exponential models. In the first approach, the global natural parameters at each node are optimized using a stochastic natural gradient that utilizes the Riemannian geometry of the approximation space, followed by an information diffusion step for cooperation with the neighbors. In the second method, a constrained optimization formulation for distributed estimation is established in natural parameter space and solved by alternating direction method of multipliers (ADMM). An application of the distributed inference/estimation of a Bayesian Gaussian mixture model is then presented, to evaluate the effectiveness of the proposed algorithms. Simulations on both synthetic and real datasets demonstrate that the proposed algorithms have excellent performance, which are almost as good as the corresponding centralized VB algorithm relying on all data available in a fusion center.

关键词： Alternating direction method of multipliers distributed algorithm stochastic natural gradient variational Bayes wireless sensor network (WSN)

来源：评论

学校读者我要写书评

暂无评论

Precise Analysis of Epidemic algorithms

Precise Analysis of Epidemic Algorithms

引用

作者： Anatolii Kostrygin Universite Paris-Saclay ECOLE POLYTECHNIQUE

学位级别：博士

In epidemic algorithms the agents in the network involve peers similarly to the spread of epi- demics. In this work, we focus on the randomized rumor spreading? a class of epidemic algorithms. We suppose that nodes of the network communicate with neigh- bors chosen at random. This approach has found nu- merous applications from the consistency maintenance of replicated databases to news spreading in social net- works. Numerous mathematical analyses of di? erent ru- mor spreading protocols can be found in the literature. Although some of them provide extremely sharp esti- mates for the performance of such processes, most of them are based on the inherent properties of concrete protocols. We develop new simple and generic method to ana- lyze randomized rumor spreading processes in complete graphs. In contrast to all previous works, we only need to understand the probability and the covariance of the events that uninformed nodes learn the rumor. This uni- versality allows us to easily analyze the classic push, pull, and push-pull protocols in their pure version as well as in several variations such as when messages fail with constant probability or when nodes call a random number of others each round. Some dynamic models can also be analyzed, e. g., when the network is a random graph sampled independently each round [Clementi et al. (ESA 2013)]. Despite this generality, our method de- termines the expected rumor spreading time precisely apart from additive constants, i. e., more precise than almost all previous works. We show that a deviation from the expectation by more than r rounds occurs with probability at most exp(−Ω(r)). We further use our method to discuss the assumption that nodes can answer any number of incoming calls. Restricting that only one call can be answered, we ob- serve a signi? cant increase of the runtime of the push- pull protocol. In particular, the double logarithmic end phase of the process now takes logarithmic time. This also increases the m

关键词： distributed algorithm epidemic algorithm rumor spreading dynamic graph

来源：评论

学校读者我要写书评

暂无评论

Iterative distributed algorithms for Real-Time Available Transfer Capability Assessment of Multiarea Power Systems

引用

IEEE TRANSACTIONS ON SMART GRID 2015年第5期6卷 2569-2578页

作者： Liu, Jian-Hong Chu, Chia-Chi Natl Tsing Hua Univ Dept Elect Engn Hsinchu 300 Taiwan

This paper studies iterative distributed algorithms for real-time available transfer capability (ATC) assessment in energy management systems of multiarea power systems. Since ATC calculations can be modeled as a special nonlinear optimal power-flow problem, iterative decomposition-coordination approaches based on constrained augmented Lagrangian methods can be applied. One special distributed scheme, called the auxiliary problem principle method, will be studied for distributed ATC assessment in this paper. A computation framework of this distributed algorithm is investigated. System partition with nonoverlapping and boundary sub-systems will also be studied. Simulations of several IEEE test systems will be conducted to validate the feasibility and the correctness of this distributed ATC. In addition, the real-time monitoring and reaction mechanism of this distributed algorithm will also be demonstrated by numerical experiments.

关键词： Approximate constrained augmented Lagrangian auxiliary problem principle method (APPM) available transfer capability (ATC) distributed algorithm system partition

来源：评论

学校读者我要写书评

暂无评论

On the Feasibility of distributed Kernel Regression for Big Data

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2016年第11期28卷 3041-3052页

作者： Xu, Chen Zhang, Yongquan Li, Runze Wu, Xindong Univ Ottawa Dept Math & Stat Ottawa ON K1N 6N5 Canada China Jiliang Univ Dept Informat & Math Sci Hangzhou 310018 Zhejiang Peoples R China Penn State Univ Dept Stat State Coll PA 16801 USA Penn State Univ Methodol Ctr State Coll PA 16801 USA Univ Vermont Dept Comp Sci Burlington VT 05405 USA

In Big Data applications, massive datasets with huge numbers of observations are frequently encountered. To deal with such massive datasets, a divide-and-conquer scheme (e.g., MapReduce) is often used for the analysis of Big Data. With such a strategy, a large dataset (e.g., a centralized real database or a virtual database with distributed data sources) is first divided into smaller manageable segments;the final output is then aggregated from the individual outputs of the segments. Despite its popularity in practice, it remains largely unknown whether such a distributive strategy provides valid theoretical inferences to the original data. In this paper, we address this fundamental issue for the distributed kernel regression (DKR) problem, where the algorithmic feasibility is measured by the generalization performance of the resulting estimator. To justify DKR, a uniform convergence rate is needed for bounding the generalization error over the individual outputs, which brings new and challenging issues in the Big Data setup. Using a sample dependent kernel dictionary, we show that, with proper data segmentation, DKR leads to an estimator that is generalization consistent to the unknown regression function. This result theoretically justifies DKR and sheds light on more advanced distributive algorithms for processing Big Data. The promising performance of the method is supported by both simulation and real data examples.

关键词： Big data divide-and-conquer distributed algorithm generalization error kernel regression

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：