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

SIAM JOURNAL ON COMPUTING 2000年第5期29卷 1683-1702页

作者： Khanna, S Liberatore, V Univ Penn Dept Comp & Informat Sci Philadelphia PA 19104 USA Univ Maryland Inst Adv Comp Studies College Pk MD 20742 USA

Broadcast disks are an emerging paradigm for massive data dissemination. In a broadcast disk, data is divided into n equal-sized pages, and pages are broadcast in a round-robin fashion by a server. Broadcast disks are effective because many clients can simultaneously retrieve any transmitted data. Paging is used by the clients to improve performance, much as in virtual memory systems. However, paging on broadcast disks differs from virtual memory paging in at least two fundamental aspects: A page fault in the broadcast disk model has a variable cost that depends on the requested page as well as the current state of the broadcast. Prefetching is both natural and a provably essential mechanism for achieving significantly better competitive ratios in broadcast disk paging. In this paper, we design a deterministic algorithm that uses prefetching to achieve an O(n log k) competitive ratio for the broadcast disk paging problem, where k denotes the size of the client's cache. We also show a matching lower bound of Omega(n log k) that applies even when the adversary is not allowed to use prefetching. In contrast, we show that when prefetching is not allowed, no deterministic online algorithm can achieve a competitive ratio better than Omega(nk). Moreover, we show a lower bound of Omega(n log k) on the competitive ratio achievable by any nonprefetching randomized algorithm against an oblivious adversary. These lower bounds are trivially matched from above by known results about deterministic and randomized marking algorithms for paging. An interpretation of our results is that in the broadcast disk paging, prefetching is a perfect substitute for randomization.

关键词： design of algorithms online algorithms competitive analysis paging distributed systems client-server architecture broadcast disks

来源：评论

学校读者我要写书评

暂无评论

A simple analysis of the harmonic algorithm for two servers

引用

INFORMATION PROCESSING LETTERS 2000年第1-2期75卷 75-77页

作者： Chrobak, M Sgall, J Univ Calif Riverside Dept Comp Sci Riverside CA 92521 USA Acad Sci Czech Republic Inst Math CZ-11567 Prague 1 Czech Republic Charles Univ Prague Fac Math & Phys Dept Appl Math Prague Czech Republic

HARMONIC is a randomized k-server algorithm that chooses the servers with probabilities proportional to the inverses of distances to the request paint. We present a simple proof that HARMONIC is 3-competitive for k = ... 详细信息

关键词： analysis of algorithms theory of computation online algorithms randomization

来源：评论

学校读者我要写书评

暂无评论

Randomized online scheduling with delivery times

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 1999年第4期3卷 399-416页

作者： Seiden, S Max Planck Inst Informat D-66123 Saarbrucken Germany

We study one of the most basic online scheduling models, online one machine scheduling with delivery times where jobs arrive over time. We provide the first randomized algorithm for this model, show that it is 1.55370-competitive and show that this analysis is tight. The best possible deterministic algorithm is phi approximate to 1.61803-competitive. Our algorithm is a distribution between two deterministic algorithms. We show that any such algorithm is no better than 1.5-competitive. To our knowledge, this is the first lower bound proof for a distribution between two deterministic algorithms.

关键词： analysis of algorithms online algorithms scheduling

来源：评论

学校读者我要写书评

暂无评论

Estimating the range of a function in an online setting

引用

INFORMATION PROCESSING LETTERS 1999年第1-2期72卷 31-35页

作者： Mount, JA 552 Melrose Ave. San Francisco CA 94127-2220 USA

Consider an unknown function L(.):{1,..., d}-->{1,..., r}with range R = {L(i)\i = 1,..., d}. Given d, r, epsilon, delta > 0 we show how to compute an estimate (p) over tilde such that with probability at least 1 - delta we have \\R\/r-(p) over tilde\ less than or equal to epsilon (p) over tilde. This is an estimate with a fixed relative error, which is stronger than finding an estimate with a fixed absolute error. This calculation can be performed efficiently in one pass through the domain of L (allowing the the method to be used in online situations) using only O(logr(loglogr + log 1/delta)/epsilon(2)) words of storage. The method is based on pairwise-independent pseudo-random variables. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： analysis of algorithms online algorithms pairwise independence pseudo-random generation randomized algorithms sampling

来源：评论

学校读者我要写书评

暂无评论

On wirelength estimations for row-based placement

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 1999年第9期18卷 1265-1278页

作者： Caldwell, AE Kahng, AB Mantik, S Markov, IL Zelikovsky, A Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90095 USA Georgia State Univ Dept Comp Sci Atlanta GA 30303 USA

Wirelength estimation in very large scale integration layout is fundamental to any predetailed routing estimate of timing or routability. In this paper, we develop efficient wirelength estimation techniques appropriate for wirelength estimation during top-down floorplanning and placement of cell-based designs. Our methods give accurate, linear-time approaches, typically with sublinear time complexity for dynamic updating of estimates (e.g,, for annealing placement). Our techniques offer advantages not only for early on-line wirelength estimation during top down placement, but also for a posteriori estimation of routed wirelength given a final placement. In developing these new estimators, we have made several contributions, including 1) insight into the contrast between region-based and bounding box-based rectilinear Steiner minimal tree (RStMT) estimation techniques;2) empirical assessment of the correlations between pin placements of a multipin net that is contained in a block;and 3) new wirelength estimates that are functions of a block's complexity (number of cell instances) and aspect ratio.

关键词： interconnect estimation online algorithms row-based placement standard cell placement Steiner-tree top-down placement very large scale integration (VLSI) wirelength estimation

来源：评论

学校读者我要写书评

暂无评论

On-line routing in all-optical networks

引用

THEORETICAL COMPUTER SCIENCE 1999年第1-2期221卷 19-39页

作者： Bartal, Y Leonardi, S Univ Roma La Sapienza Dipartimento Informat & Sistemist I-00198 Rome Italy Int Comp Sci Inst Berkeley CA 94704 USA Int Comp Sci Inst Berkeley CA 94704 USA Univ Calif Berkeley Berkeley CA 94704 USA

The paper deals with on-line routing in wavelength division multiplexing (WDM) optical networks. A sequence of requests arrives over time, each is a pair of nodes to be connected by a path. The problem is to assign a wavelength and a path to each pair, so that no two paths sharing a link are assigned the same wavelength. The goal is to minimize the number of wavelengths used to establish all connections. Raghavan and Upfal (Proc. 26th Annual Symp. on Theory of Computing, 1994, pp. 133-143) considered the off-line version of the problem, which was further studied in Aumann and Rabani (Proc. 6th ACM-SIAM Symp. on Discrete algorithms, 1995, pp. 567-576), Kaklamanis and Persiano (Proc. 4th Annual European Symp. on algorithms, Lecture Notes in Computer Science, vol. 1136, Springer, Berlin, 1996, pp. 460-470), Mihail et al. (Proc. 36th IEEE Annual Symp. on Foundations of Computer Science, 1995, pp. 548-557), Rabani, (Proc. 37th Annual Symp. on Foundations of Computer Science, 1996, pp. 400-409). For a line topology, the problem is the well-studied interval graph coloring problem. On-line algorithms for this problem have been analyzed in Kierstead and Trotter (Congr. Numer. 33 (1981) 143-153). We consider trees, trees of rings, and meshes topologies, previously studied in the off-line case. We give on-line algorithms with competitive ratio O(log n) for all these topologies. We give a matching Omega(log n) lower bound for meshes. We also prove that any algorithm for trees cannot have competitive ratio better than Omega(log n/log log n). We also consider the problem where every edge is associated with parallel links. While in WDM technology, a fiber link requires different wavelengths for every transmission, space division multiplexing technology allows parallel links for a single wavelength, at an additional cost. Thus, it may be beneficial in terms of network economics to combine between the two technologies (this is indeed done in practice). For arbitrary networks with Om

关键词： online algorithms competitive analysis routing optical networks

来源：评论

学校读者我要写书评

暂无评论

Bandwidth allocation with preemption

引用

SIAM JOURNAL ON COMPUTING 1999年第5期28卷 1806-1828页

作者： Bar-Noy, A Canetti, R Kutten, S Mansour, Y Schieber, B Tel Aviv Univ Dept Elect Engn IL-69978 Tel Aviv Israel IBM Corp Div Res Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA MIT Comp Sci Lab Cambridge MA 02139 USA Technion Israel Inst Technol Dept Ind Engn IL-32000 Haifa Israel

Bandwidth allocation is a fundamental problem in the design of networks where bandwidth has to be reserved for connections in advance. The problem is intensified when the overall requested bandwidth exceeds the capacity and not all requests can be served. Furthermore, acceptance/rejection decisions regarding connections have to be made online, without knowledge of future requests. We show that the ability to preempt (i.e., abort) connections while in service in order to schedule "more valuable" connections substantially improves the throughput of some networks. We present bandwidth allocation strategies that use preemption and show that they achieve constant competitiveness with respect to the throughput, given that any single call requests at most a constant fraction of the bandwidth. Our results should be contrasted with recent works showing that nonpreemptive strategies have at most inverse logarithmic competitiveness.

关键词： bandwidth allocation online algorithms preemption call control call admission

来源：评论

学校读者我要写书评

暂无评论

On-line approximation algorithms for scheduling tasks on identical machines with extendable working time

引用

ANNALS OF OPERATIONS RESEARCH 1999年第86期86卷 491-506页

作者： Speranza, MG Tuza, Z Dept Quantitat Methods I-25122 Brescia Italy Hungarian Acad Sci Inst Comp & Automat H-1111 Budapest Hungary

We study the on-line problem of assigning tasks to identical machines whose regular working time - assumed to be unitary - can be extended. If the tasks assigned to a machine do not exceed the regular working time, then the working time of the machine is considered to be 1;otherwise, it is the completion time of the last task assigned to the machine. Each incoming task has to be assigned immediately to a machine and the assignment cannot be changed later. The objective is to minimize the sum of the working times of the machines. Since the regular working time of the machines can be seen as a given capacity, the problem can also be described through the bin packing terminology: the machines are viewed as bins and the tasks as items. A lower bound of 7/6 on the worst-case relative error of any on-line algorithm is shown. Then it is shown that a list scheduling heuristic which assigns the incoming task to the machine with smallest current load has worst-case error equal to 5/4. The bound is improved to 1.228 by a new algorithm which tends to load the partially loaded machines, as long as this does not cause an increase of the working time by more than a fixed and appropriately chosen quantity x > 0.

关键词： scheduling on identical machines extendable working time bin packing online algorithms worst-case performance

来源：评论

学校读者我要写书评

暂无评论

On-line routing in all-optical networks 24th

引用

24th International Colloquium on Algorithm, Languages and Programming (ICALP 97)

ISBN: (纸本)3540631658

关键词： online algorithms competitive analysis routing optical networks

来源：评论

学校读者我要写书评

暂无评论

Ondashline routing in all-optical networks

引用

Theoretical Computer Science 1999年第1-2期221卷 19-39页

作者： Yair Bartal Stefano Leonardi U.C. Berkeley and International Computer Science Institute (ICSI) Berkeley CA 94704 USA Dipartimento di Informatica e Sistemistica Universitàdi Roma “La Sapienza” Via Salaria 113 I-00198 Roma Italy

The paper deals with ondashline routing in wavelength division multiplexing (WDM) optical networks. A sequence of requests arrives over time, each is a pair of nodes to be connected by a path. The problem is to assign a wavelength and a path to each pair, so that no two paths sharing a link are assigned the same wavelength. The goal is to minimize the number of wavelengths used to establish all connections. Raghavan and Upfal (Proc. 26th Annual Symp. on Theory of Computing, 1994, pp. 133–143) considered the off-line version of the problem, which was further studied in Aumann and Rabani (Proc. 6th ACM-SIAM Symp. on Discrete algorithms, 1995, pp. 567–576), Kaklamanis and Persiano (Proc. 4th Annual European Symp. on algorithms, Lecture Notes in Computer Science, vol. 1136, Springer, Berlin, 1996, pp. 460–470), Mihail et al. (Proc. 36th IEEE Annual Symp. on Foundations of Computer Science, 1995, pp. 548–557), Rabani, (Proc. 37th Annual Symp. on Foundations of Computer Science, 1996, pp. 400–409). For a line topology, the problem is the well-studied interval graph coloring problem. Ondashline algorithms for this problem have been analyzed in Kierstead and Trotter (Congr. Numer. 33 (1981) 143–153). We consider trees, trees of rings, and meshes topologies, previously studied in the off-line case. We give ondashline algorithms with competitive ratio O(log n ) for all these topologies. We give a matching Ω(log n ) lower bound for meshes. We also prove that any algorithm for trees cannot have competitive ratio better than Ω(log n /log log n ). We also consider the problem where every edge is associated with parallel links. While in WDM technology, a fiber link requires different wavelengths for every transmission, space division multiplexing technology allows parallel links for a single wavelength, at an additional cost. Thus, it may be beneficial in terms of network economics to combine between the two technologies (this is indeed done in practice). For arbitrary networks wi

关键词： online algorithms Competitive analysis Routing Optical networks

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：