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

Stability and performance analysis of rate-based feedback flow controlled ATM networks

QUEUEING SYSTEMS 1998年第2-4期29卷 129-159页

作者： Sharma, V Kuri, J Indian Inst Sci Dept Elect Engn Bangalore 560012 Karnataka India Ecole Polytech Dept Genie Elect & Genie Informat Montreal PQ H3C 3A7 Canada

Motivated by ABR class of service in ATM networks, we study a continuous time queueing system with a feedback control of the arrival rate of some of the sources. The feedback about the queue length or the total workload is provided at regular intervals (variations on it, especially the traffic management specification TM 4.0, are also considered). The propagation delays can be nonnegligible. For a general class of feedback algorithms, we obtain the stability of the system in the presence of one or more bottleneck nodes in the virtual circuit. Our system is general enough that it can be useful to study feedback control in other network protocols. We also obtain rates of convergence to the stationary distributions and finiteness of moments. For the single botterneck case, we provide algorithms to compute the stationary distributions and the moments of the sojourn times in different sets of states. We also show analytically (by showing continuity of stationary distributions and moments) that for small propagation delays, we can provide feedback algorithms which have higher mean throughput, lower probability of overflow and lower delay jitter than any open loop policy. Finally these results are supplemented by some computational results.

关键词： rate-based feedback control ATM networks stability optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

A note on two fixed point problems

引用

JOURNAL OF COMPLEXITY 2007年第4-6期23卷 952-961页

作者： Boonyasiriwat, Ch. Sikorski, K. Xiong, Ch. Univ Utah Sch Comp Salt Lake City UT 84112 USA Univ Utah Dept Chem Salt Lake City UT 84112 USA

We extend the applicability of the Exterior Ellipsoid Algorithm for approximating n-dimensional fixed points of directionally nonexpanding functions. Such functions model many practical problems that cannot be formulated in the smaller class of globally nonexpanding functions. The upper bound 2n(2) ln(2/epsilon) on the number of function evaluations for finding epsilon-residual approximations to the fixed points remains the same for the larger class. We also present a modified version of a hybrid bisection-secant method for efficient approximation of univariate fixed point problems in combustion chemistry. (c) 2007 Elsevier Inc. All rights reserved.

关键词： fixed point problems optimal algorithms nonlinear equations Ellipsoid algorithm computational complexity

来源：评论

学校读者我要写书评

暂无评论

Optimizing server placement in distributed systems in the presence of competition

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2011年第1期71卷 62-76页

作者： Wu, Jan-Jan Shih, Shu-Fan Liu, Pangfeng Chung, Yi-Min Acad Sinica Inst Informat Sci Taipei Taiwan Acad Sinica Res Ctr Informat Technol Innovat Taipei 115 Taiwan Natl Taiwan Univ Dept Comp Sci & Informat Engn Taipei 10764 Taiwan

Although the problem of data server placement in parallel and distributed systems has been studied extensively, most of the existing work assumes there is no competition between servers. Hence, their goal is to minimize read, update and storage cost. In this paper, we study the server placement problem in which a new server has to compete with existing servers for user requests. Therefore, in addition to minimizing cost, we also need to maximize the benefit of building a new server. Our major results include three parts. First, for tree-structured systems, we propose an O(vertical bar V vertical bar(3)k) time dynamic programming algorithm to find the optimal placement of k extra servers that maximizes the benefit in a tree with vertical bar V vertical bar nodes. We also propose an O(vertical bar V vertical bar(3)) time dynamic programming algorithm to find the optimal placement of extra servers that maximizes the benefit, without any constraint on the number of extra servers. Second, for general connected graphs, we prove that the server placement problems are NP-complete, and present three greedy heuristic algorithms, called Greedy Add, Greedy Remove and Greedy Add-Remove, to solve them. Third, we show that if the number of requests a server can handle (i.e., server capacity) is bounded, the server placement problem is NP-complete even for tree networks. We then derive a variation of the same set of greedy heuristic algorithms, with consideration of server capacity constraint, to solve the problem. Our experiment results demonstrate that the greedy algorithms achieve good results, when compared with the upper bounds found by a linear programming algorithm. Greedy Add performs best in the unconstrained model, yielding a benefit within 12% difference from the theoretical upper bound in average. For the constrained model, Greedy Remove performs best for smaller network sizes, while Greedy Add-Remove performs best for larger network sizes. On average, the heuristic alg

关键词： Competition-aware server placement Resource allocation Distributed system Grid and Cloud Maximizing benefit Minimizing construction cost optimal algorithms Heuristic algorithms

来源：评论

学校读者我要写书评

暂无评论

algorithms for testing occurrences of length 4 patterns in permutations

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2018年第1期35卷 189-208页

作者： Han, Yijie Saxena, Sanjeev Univ Missouri Sch Comp & Engn Kansas City MO 64110 USA Indian Inst Technol Dept Comp Sci & Engn Kanpur 208016 Uttar Pradesh India

In this paper linear time sequential and optimal parallel algorithms for testing pattern involvement for all length 4 permutations are described. This is an improvement as the previous best sequential algorithms, for most of these pattern require time. Our parallel algorithms can be implemented in time with processors on the CREW PRAM model, or alternatively in time with processors on a CRCW PRAM PRAM model. Parallel algorithm can also be implemented in constant time with processors on a CRCW PRAM model. The previous best parallel algorithms were available for only some of these patterns and took time with n processors on the CREW PRAM model.

关键词： Separable permutations Length 4 permutations Pattern matching optimal algorithms Parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Parallel self-index integer sorting

引用

JOURNAL OF SUPERCOMPUTING 2002年第3期22卷 269-275页

作者： Bahig, HM Daoud, SS Khairat, MKA Ain Shams Univ Fac Sci Dept Math Cairo Egypt

We consider the problem of sorting n integers when the elements are drawn from the restricted domain [1...n]. A new deterministic parallel algorithm for sorting n integers is obtained. Its running time is O(log n log(n/log n)) using n/log n processors on EREW (exclusive read exclusive write) PRAM (parallel random access machine). Also, our algorithm was modified to become optimal when we use rootn processors. This algorithm belongs to class EP (Efficient, Polynomial fast).

关键词： parallel algorithms self-index integer sorting EREW PRAM optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

Bridging Supervised Learning and Test-Based Co-optimization

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2017年第1期18卷 1255-1293页

作者： Popovici, Elena Icosyst Corp 222 Third StSuite 0142 Cambridge MA 02142 USA

This paper takes a close look at the important commonalities and subtle differences between the well-established field of supervised learning and the much younger one of cooptimization. It explains the relationships between the problems, algorithms and views on cost and performance of the two fields, all throughout providing a two-way dictionary for the respective terminologies used to describe these concepts. The intent is to facilitate advancement of both fields through transfer and cross-pollination of ideas, techniques and results. As a proof of concept, a theoretical study is presented on the connection between existence / lack of free lunch in the two fields, showcasing a few ideas for improving computational complexity of certain supervised learning approaches.

关键词： supervised learning active learning co-optimization free lunch optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

ON THE CRUDE MULTIDIMENSIONAL SEARCH

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 1994年第3期56卷 283-293页

作者： SOBOL, IM BAKIN, SG RUSSIAN ACAD SCI INST MATH MODELLINGMOSCOW 125047RUSSIA

Multivariable trial functions that depend on random parameters are maximized by crude global search. Analytical and numerical investigations of error distributions confirm recent conclusions that in practice random searching points perform better than rectangular lattices, and that quasi-random searching points are even more efficient.

关键词： OPTIMIZATION optimal algorithms CRUDE SEARCH RANDOM SEARCH QUASI-RANDOM SEARCH

来源：评论

学校读者我要写书评

暂无评论

The minimum k-storage problem on directed graphs

引用

THEORETICAL COMPUTER SCIENCE 2015年 596卷 102-108页

作者： D'Angelo, Gianlorenzo Diodati, Daniele Navarra, Alfredo Pinotti, Cristina M. Gran Sasso Sci Inst GSSI I-67100 Laquila Italy Univ Perugia Dipartimento Matemat & Informat I-06123 Perugia Italy

In standard sensor network applications, sensors generate raw data that have to be sent to a sink node. In order to save energy, special intermediate storage nodes can be exploited in order to compress data before forwarding them to the sink. We consider the problem of locating k storage nodes in order to minimize the energy consumed for converging data to the sink. This is known as the minimum k-storage problem. We show that in directed graphs (and in particular in Directed Acyclic Graphs) the problem does not admit an algorithm with a constant approximation ratio, unless P = NP. If the topology is restricted to trees where the arcs are directed towards the sink (typical scenario in sensor networks), the problem is solvable in polynomial time. We give a dynamic programming algorithm that requires O (min{kn(2), k(2)P}) time, where n and P are the number of nodes and the path length of the tree [7], respectively. We improve over a previous algorithm which requires O (kn(2)(max{k, d})(d-1)) time, where d is the maximum out-degree of the tree [8]. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Wireless sensor networks Storage placement optimal algorithms Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

WORST-CASE optimalITY OF SMOOTHING algorithms FOR PARAMETRIC SYSTEM-IDENTIFICATION

引用

AUTOMATICA 1995年第5期31卷 759-763页

作者： TEMPO, R CENS-CNR Politecnico di Torino 10129 Torino Corso Duca degli Abruzzi 24 Italy

We study parametric identification of uncertain systems in a deterministic setting. We assume that the problem data and the linearly parameterized system model are given, In the presence of a priori information and norm-bounded noise, we design optimal worst-case algorithms. In particular, we study the interplay between identification tools and nonstandard techniques used in approximation theory. The obtained estimators, called smoothing algorithms, as well as the identification errors are computed by means of the singular-value decomposition of the system model. Finally, the proposed algorithms are tested on real data referring to the tuning of A/D converters.

关键词： SYSTEM PARAMETRIC IDENTIFICATION WORST-CASE optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

THE VLSI optimalITY OF THE AKS SORTING NETWORK

引用

INFORMATION PROCESSING LETTERS 1985年第2期20卷 55-59页

作者： BILARDI, G PREPARATA, FP Coordinated Science Laboratory University of Illinois at Urbana-Champaign Urbana IL 61801 U.S.A.

It is shown that the AKS sorting network can indeed be laid out in area A equals O(n**2), while maintaining an O(log n) computation time, thereby establishing its optimality in the VLSI model of computation.

关键词： VLSI complexity area-time trade-off sorting networks optimal algorithms parallel computation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：