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

A Parallel Computing Framework for Finding the Supported Solutions to a Biobjective network Optimization Problem

JOURNAL OF MULTI-CRITERIA DECISION ANALYSIS 2015年第5-6期22卷 244-259页

作者： Medrano, Fernando Church, Richard Univ Calif Santa Barbara Dept Geog 1832 Ellison Hall Santa Barbara CA 93106 USA

Solving multi-objective combinatorial optimization problems can quickly become computationally challenging when applied to large networks generated from big data. Present-day first-rate Mixed Integer Programming (MIP) solvers have parallelism built-in to take advantage of multicore architectures;but specialized network optimization algorithms that can often solve graph problems more efficiently than a general MIP solver are typically programmed serially. Thus, these network algorithm implementations do not take full advantage of modern multicore computer capabilities. Many parallel computing languages include a fork/join framework into their concurrency packages that allow for simple conversion of recursive serial algorithms to operate in parallel without having to use complicated low-level message-passing interfaces. Fork/join is particularly well suited to divide and conquer algorithms such as Non-Inferior Set Estimation (NISE) method for computing the supported Pareto front of a multi-objective optimization problem. This work develops a simple general parallel NISE (pNISE) implementation using the Java 7 concurrency tools, and then offers results from a specific implementation of solving a bi-objective shortest path problem. The results indicate that this method is capable of sizeable speed-ups on both small-scale personal computers as well as large-scale shared memory supercomputers. Finally, other network problems suitable to this method are discussed, including multi-objective variants of the minimum spanning tree problem, transportation problem, assignment problem, maximum flow problem, and the minimum-cost flow problem. Copyright (C) 2015 John Wiley & Sons, Ltd.

关键词： multicriteria analysis biobjective shortest paths parallel computing GIS network algorithms

来源：评论

学校读者我要写书评

暂无评论

Construction and Impromptu Repair of an MST in a Distributed network with o(m) Communication 15

Construction and Impromptu Repair of an MST in a Distributed...

引用

34th Annual ACM Symposium on Principles of Distributed Computing (PODC)

作者： King, Valerie Kutten, Shay Thorup, Mikkel Univ Victoria Comp Sci Victoria BC Canada Technion Fac IE & M IL-32000 Haifa Israel Univ Copenhagen Copenhagen Denmark

ISBN: (纸本)9781450336178

In the CONGEST model, a communications network is an undirected graph whose n nodes are processors and whose m edges are the communications links between processors. At any given time step, a message of size O(log n) may be sent by each node to each of its neighbours. We show for the synchronous model: If all nodes start in the same round, and each node knows its ID and the ID's of its neighbors, or in the case of MST, the distinct weights of its incident edges and knows n, then there are Monte Carlo algorithms which succeed w.h.p. to determine a minimum spanning forest (MST) and a spanning forest (ST) using O(n log(2) n/log log n) messages for MST and O (n log n) messages for ST, resp. These results contradict the "folk theorem" noted in Awerbuch, ***., JACM 1990 that the distributed construction of a broadcast tree requires Omega(m) messages. This lower bound has been shown there and in other papers for some CONGEST models;our protocol demonstrates the limits of these models. A dynamic distributed network is one which undergoes online edge insertions or deletions. We also show how to repair an MST or ST in a dynamic network with asynchronous communication. An edge deletion can be processed in O(n log n= log log n) expected messages in the MST, and O(n) expected messages for the ST problem, while an edge insertion uses O(n) messages in the worst case. We call this "impromptu" updating as we assume that between processing of edge updates there is no preprocessing or storage of additional information. Previous algorithms for this problem that use an amortized o(m) messages per update require substantial preprocessing and additional local storage between updates.

关键词： spanning tree distributed algorithms message complexity network algorithms

来源：评论

学校读者我要写书评

暂无评论

An analytical method for cost analysis in multi-stage supply chains: A stochastic network model approach

引用

APPLIED MATHEMATICAL MODELLING 2014年第11-12期38卷 2819-2836页

作者： Li, Chong Fuzhou Univ Sch Management Fuzhou 350108 Peoples R China

This paper studies the cost distribution characteristics in multi-stage supply chain networks. Based on the graphical evaluation and review technique, we propose a novel stochastic network mathematical model for cost distribution analysis in multi-stage supply chain networks. Further, to investigate the effects of cost components, including the procurement costs, inventory costs, shortage costs, production costs and transportation costs of supply chain members, on the total supply chain operation cost, we propose the concept of cost sensitivity and provide corresponding algorithms based on the proposed stochastic network model. Then the model is extended to analyze the cost performance of supply chain robustness under different order compensation ability scenarios and the corresponding algorithms are developed. Simulation experiment shows the effectiveness and flexibility of the proposed model, and also promotes a better understanding of the model approach and its managerial implications in cost management of supply chains. (C) 2013 Elsevier Inc. All rights reserved.

关键词： Supply chain networks Stochastic network mathematical model network algorithms Cost sensitivity analysis Cost management

来源：评论

学校读者我要写书评

暂无评论

Improved Distributed Approximate Matching

引用

JOURNAL OF THE ACM 2015年第5期62卷 38-38页

作者： Lotker, Zvi Patt-Shamir, Boaz Pettie, Seth Ben Gurion Univ Negev Dept Commun Syst Engn IL-84105 Beer Sheva Israel Tel Aviv Univ Sch Elect Engn IL-69978 Tel Aviv Israel Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48109 USA

We present distributed network algorithms to compute weighted and unweighted matchings with improved approximation ratios and running times. The computational model is a network of processors exchanging O(log n)-bit messages (the CONGEST model). For unweighted graphs, we give an algorithm providing (1 - epsilon)-approximation in O(log n) time for any constant epsilon > 0, improving on the classical 1/2-approximation in Olog n) time of Israeli and Itai [1986]. The time complexity of the algorithm depends on 1/epsilon exponentially in the general case, and polynomially in bipartite graphs. For weighted graphs, we present another algorithm which provides (1/2 - epsilon) approximation in general graphs in O(log epsilon(-1) log n) time, improving on the previously known algorithms which attain (1/4 - epsilon)-approximation in O(log n) time or 1/2-approximation in O(n) time. All our algorithms are randomized: the complexity bounds hold both with high probability and for the expected running time.

关键词： Theory CONGEST model network algorithms

来源：评论

学校读者我要写书评

暂无评论

Improved Distributed Steiner Forest Construction 14

Improved Distributed Steiner Forest Construction

引用

ACM Symposium on Principles of Distributed Computing (PODC)

作者： Lenzen, Christoph Patt-Shamir, Boaz MIT 32 Vassar St Cambridge MA 02139 USA Tel Aviv Univ IL-69978 Tel Aviv Israel

ISBN: (纸本)9781450329446

We present new distributed algorithms for constructing a Steiner Forest in the congest model. Our deterministic algorithm finds, for any given constant epsilon > 0, a (2 + epsilon)-approximation in (O)over tilde(sk + p root min {st;n})) rounds, where s is the shortest path diameter, t is the number of terminals, k is the number of terminal components in the input, and n is the number of nodes. Our randomized algorithm finds, with high probability, an O (log n)-approximation in time (O)over tilde(k + min {s;root n} + D), where D is the unweighted diameter of the network. We also prove a matching lower bound of (Omega)over tilde(k + min {s;root n} + D) on the running time of any distributed approximation algorithm for the Steiner Forest problem. Previous algorithms were randomized, and obtained either an O(log n)-approximation in (O)over tilde(sk) time, or an O(1/epsilon)-approximation in (O)over tilde((root n + t)(1+epsilon) + D) time.

关键词： network algorithms steiner tree congest model minimum spanning tree}

来源：评论

学校读者我要写书评

暂无评论

UPS: Universal Protocol Stack for emerging wireless networks

引用

AD HOC networkS 2013年第2期11卷 687-700页

作者： Feng, Chen-Hsiang Demirkol, Ilker Heinzelman, Wendi B. Univ Rochester Dept Elect & Comp Engn Rochester NY 14627 USA

Recent devices developed for emerging wireless networks, such as 4G cellular networks, wireless mesh networks, and mobile ad hoc networks, support multiple communication substrates and require execution of multiple protocols within a layer, which cannot be supported efficiently by traditional, layered protocol stack approaches. While cross-layer approaches can be designed to support these new requirements, the lack of modularity makes cross-layer approaches inflexible and hence difficult to adapt for future devices and protocols. Thus, there is a need for a new protocol architecture to provide universal support for cross-layer interactions between layers, while also supporting multiple communication substrates and multiple protocols within a stack. In this paper, we propose Universal Protocol Stack (UPS), which provides such support in a modular way through packet-switching, information-sharing and memory management. To show that UPS is realizable with very low overhead and that it enables concurrent and independent execution of protocols of the same stack layer, first, we present a wireless sensor network test-bed evaluation, where UPS is implemented in TinyOS and installed on individual sensor motes. Two cross-layer routing protocols are implemented and evaluated with UPS and without UPS. We also implemented UPS in the OPNET simulator, where the IP (e.g., Routing Information Protocol (RIP)) and AODV routing protocols are executed concurrently to support networks with both static and mobile wireless nodes. Our implementation shows that the overhead incurred to implement UPS is very low, and little or no modification is required to adapt existing protocols to the UPS framework. Both studies also show the advantage of enabling concurrent protocol execution within a stack layer, improving the successful packet delivery ratio or the total number of packets sent for the investigated scenarios. Published by Elsevier B.V.

关键词： Protocol design network algorithms Wireless communication network protocol stack

来源：评论

学校读者我要写书评

暂无评论

Gossip Protocols for Renaming and Sorting 1

引用

27th International Symposium on Distributed Computing (DISC)

作者： Giakkoupis, George Kermarrec, Anne-Marie Woelfel, Philipp INRIA Rennes Bretagne Atlantic Rennes France Univ Calgary Dept Comp Sci Calgary AB Canada

ISBN: (数字)9783642415272

ISBN: (纸本)9783642415272;9783642415265

We devise efficient gossip-based protocols for some fundamental distributed tasks. The protocols assume an n-node network supporting point-to-point communication, and in every round, each node exchanges information of size O(log n) bits with (at most) one other node. We first consider the renaming problem, that is, to assign distinct IDs from a small ID space to all nodes of the network. We propose a renaming protocol that divides the ID space among nodes using a natural push or pull approach, achieving logarithmic round complexity with ID space {1, ... , (1 + epsilon)n}, for any fixed epsilon > 0. A variant of this protocol solves the tight renaming problem, where each node obtains a unique ID in {1,..., n}, in O(log(2) n) rounds. Next we study the following sorting problem. Nodes have consecutive IDs 1 up to n, and they receive numerical values as inputs. They then have to exchange those inputs so that in the end the input of rank k is located at the node with ID k. Jelasity and Kermarrec [20] suggested a simple and natural protocol, where nodes exchange values with peers chosen uniformly at random, but it is not hard to see that this protocol requires Omega(n) rounds. We prove that the same protocol works in O(log(2) n) rounds if peers are chosen according to a non-uniform power law distribution.

关键词： renaming sorting gossip protocols epidemic protocols distributed algorithms randomized algorithms network algorithms

来源：评论

学校读者我要写书评

暂无评论

Special issue on advances in communications and networking - II

引用

Journal of Communications 2012年第1期7卷 1-2页

作者： Zhai, Fan Matta, Ibrahim Rouskas, George Texas Instruments United States Boston University United States North Carolina State University United States

来源：评论

学校读者我要写书评

暂无评论

Why locally-fair maximal flows in client-server networks perform well

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2011年第3期22卷 426-437页

作者： Berman, Kenneth A. Yoshikawa, Chad Univ Cincinnati Dept Comp Sci Cincinnati OH 45221 USA

Maximal flows reach at least a 1/2 approximation of the maximum flow in client-server networks. By adding 1 additional time round to any distributed maximal flow algorithm we show how this 1/2-approximation can be improved on bounded-degree networks. We call these modified maximal flows 'locally fair' since there is a measure of fairness prescribed to each client and server in the network. Let N=(U,V,E,b) represent a client-server network with clients U, servers V, network links E, and node capacities b, where we assume that each capacity is at least one unit. Let d(u) denote the b-weighted degree of any node uaUa(a)V, Delta=max {d(u)|uaU} and delta=min {d(v)|vaV}. We show that a locally-fair maximal flow f achieves an approximation to the maximum flow of min{1, Delta(2)-delta/2 Delta(2)-delta Delta-Delta}, and this result is sharp for any given integers delta and Delta. This results are of practical importance since local-fairness loosely models the steady-state behavior of TCP/IP and these types of degree-bounds often occur naturally (or are easy to enforce) in real client-server systems.

关键词： Distributed flow algorithms Oblivious routing network algorithms Maximal flow

来源：评论

学校读者我要写书评

暂无评论

algorithms for optimizing the bandwidth cost of content delivery

引用

COMPUTER networkS 2011年第18期55卷 4007-4020页

作者： Adler, Micah Sitaraman, Ramesh K. Venkataramani, Harish Univ Massachusetts Dept Comp Sci Amherst MA 01003 USA Google Inc Mountain View CA 94043 USA Fiksu Inc Boston MA 02110 USA

Content Delivery networks (CDNs) deliver web content to end-users from a large distributed platform of web servers hosted in data centers belonging to thousands of Internet Service Providers (ISPs) around the world. The bandwidth cost incurred by a CDN is the sum of the amounts it pays each ISP for routing traffic from its servers located in that ISP out to end-users. A large enterprise may also contract with multiple ISPs to provide redundant Internet access for its origin infrastructure using technologies such as multihoming and mirroring, thereby incurring a significant bandwidth cost across multiple ISPs. This paper initiates the formal algorithmic study of bandwidth cost minimization in the context of a large enterprise or a CDN, a problem area that is both algorithmically rich and practically very important. First, we model different types of contracts that are used in practice by ISPs to charge for bandwidth usage, including average, maximum, and 95th-percentile contracts. Then, we devise an optimal offline algorithm that routes traffic to achieve the minimum bandwidth cost, when the network contracts charge either on a maximum or on an average basis. Next, we devise a deterministic (resp., randomized) online algorithm that achieves cost that is within a factor of 2 (resp., e/e-1) of the optimal offline cost for maximum and average contracts. In addition, we prove that our online algorithms achieve the best possible competitive ratios in both the deterministic and the randomized cases. An interesting theoretical contribution of this work is that we show intriguing connections between the online bandwidth optimization problem and the seemingly-unrelated but well-studied ski rental problem where similar optimal competitive ratios are known to hold. Finally, we consider extensions for contracts with a committed amount of spend (known as committed information rate or CIR) and contracts that charge on a 95th-percentile basis. (C) 2011 Elsevier B.V. All rights rese

关键词： Internet content delivery Content Delivery networks Optimization algorithms Bandwidth cost minimization network algorithms Traffic management algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：