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

Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures

作者： Amotz Bar-Noy Justin Goshi Richard E. Ladner Brooklyn College -- CUNY Brooklyn NY University of Washington Seattle WA

ISBN: (纸本)9781581136616

We address the problem of designing efficient solutions for media-on-demand in systems that use stream merging. In a stream merging system, the receiving bandwidth of clients is larger than the playback bandwidth and clients can buffer parts of the transmission to be played back later. Intelligent use of these resources allows bandwidth usage to be reduced exponentially over traditional unicast delivery of popular media. We design an off-line algorithm that, in O(n) time, computes an optimal off-line stream merging solution for the case when the time horizon n is known ahead of time. In addition, we describe an on-line delay guaranteed solution that operates without knowledge of the time horizon size, and show that it performs asymptotically close to the optimal off-line algorithm. The on-line algorithm is simpler to implement than previously proposed on-line stream merging algorithms, and empirically performs well when the intensity of client arrivals is high.

关键词： on-line algorithms stream merging off-line algorithms media-on-demand

来源：评论

学校读者我要写书评

暂无评论

Convergent on-line algorithms for supervised learning in neural networks

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS 2000年第6期11卷 1284-1299页

作者： Grippo, L Univ Roma La Sapienza Dipartimento Informat & Sistemist Rome Italy

In this paper we define on-line algorithms for neural-network training, based on the construction of multiple copies of the network, which are trained by employing different data blocks. It is shown that suitable training algorithms can be defined, in a way that the disagreement between the different copies of the network is asymptotically reduced, and convergence toward stationary points of the global error function can be guaranteed, Relevant features of the proposed approach are that the learning rate must be not necessarily forced to zero and that real-time learning is permitted.

关键词： neural networks on-line algorithms supervised learning training algorithms unconstrained optimization

来源：评论

学校读者我要写书评

暂无评论

Fair versus unrestricted bin packing

引用

ALGORITHMICA 2002年第2期34卷 181-196页

作者： Azar, Y Boyar, J Epstein, L Favrholdt, LM Larsen, KS Nielsen, MN Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel Univ So Denmark Dept Math & Comp Sci Odense Denmark Interdisciplinary Ctr Sch Comp & Media Sci Herzliyya Israel

We consider the on-line Dual Bin Packing problem where we have n unit size bins and a sequence of items. The goal is to maximize the number of items that are packed in the bins by an on-line algorithm. We investigate unrestricted algorithms that have the power of performing admission control on the items, i.e., rejecting items while there is enough space to pack them, versus fair algorithms that reject an item only when there is not enough space to pack it. We show that by performing admission control on the items, we get better performance compared with the performance achieved on the fair version of the problem. Our main result shows that with an unfair variant of First-Fit, we can pack approximately two-thirds of the items for sequences for which an optimal off-line algorithm can pack all the items. This is in contrast to standard First-Fit where we show an asymptotically tight hardness result: if the number of bins can be chosen arbitrarily large, the fraction of the items packed by First-Fit comes arbitrarily close to five-eighths.

关键词： on-line algorithms competitive analysis bin packing dual bin packing restricted adversaries randomization admission control

来源：评论

学校读者我要写书评

暂无评论

On an on-line scheduling problem for parallel jobs

引用

INFORMATION PROCESSING LETTERS 2002年第6期81卷 297-304页

作者： Naroska, E Schwiegelshohn, U Univ Dortmund Comp Engn Inst D-44221 Dortmund Germany

This paper addresses the non-preemptive on-line scheduling of parallel jobs. In particular we assume that the release dates and the processing times of the jobs are unknown. It is already known that for this problem Garey and Graham's list scheduling algorithm achieves the competitive factor 2 - 1/m for the makespan if m identical machines are available and if each job requires only a single machine for processing. Here, we show that the same factor also holds in the case of parallel jobs. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： on-line algorithms analysis of algorithms scheduling

来源：评论

学校读者我要写书评

暂无评论

Optimal time-critical scheduling via resource augmentation

引用

ALGORITHMICA 2002年第2期32卷 163-200页

作者： Phillips, CA Stein, C Torng, E Wein, J Sandia Natl Labs Albuquerque NM 87183 USA Columbia Univ Dept Ind Engn & Operat Res New York NY 10027 USA Dartmouth Coll Hanover NH 03755 USA Stanford Univ Stanford CA 94305 USA Michigan State Univ Dept Comp Sci & Engn E Lansing MI 48824 USA Polytech Univ Dept Comp Sci Brooklyn NY 11201 USA

We consider two fundamental problems in dynamic scheduling: scheduling to meet deadlines in a preemptive multiprocessor setting, and scheduling to provide good response time in a number of scheduling environments. When viewed from the perspective of traditional worst-case analysis, no good on-line algorithms exist for these problems, and for some variants no good off-line algorithms exist unless P = NP. We study these problems using a relaxed notion of competitive analysis, introduced by Kalyanasundaram and Pruhs, in which the on-line algorithm is allowed more resources than the optimal off-line algorithm to which it is compared, Using this approach, we establish that several well-known on-line algorithms, that have poor performance from an absolute worst-case perspective, are optimal for the problems in question when allowed moderately more resources. For optimization of average flow time, these are the first results of any sort, for any NP-hard version of the problem, that indicate that it might be possible to design good approximation algorithms.

关键词： scheduling on-line algorithms competitive analysis flow time real-time extra-resources

来源：评论

学校读者我要写书评

暂无评论

On-line file caching

引用

ALGORITHMICA 2002年第3期33卷 371-383页

作者： Young, NE Dartmouth Coll Hanover NH 03755 USA Akamai Technol Cambridge MA 02138 USA

Consider the following file caching problem: in response to a sequence of requests for files, where each file has a specified size and retrieval cost, maintain a cache of files of total size at most some specified k so as to minimize the total retrieval cost. Specifically, when a requested file is not in the cache, bring it into the cache and pay the retrieval cost, and remove other files from the cache so that the total size of files remaining in the cache is at most k. This problem generalizes previous paging and caching problems by allowing objects of arbitrary Size and cost, both important attributes when caching files for world-wide-web browsers, servers, and proxies. We give a simple deterministic on-line algorithm that generalizes many well-known paging and weighted-caching strategies, including least-recently-used, first-in-first-out, flush-when-full, and the balance algorithm. On any request sequence, the total cost incurred by the algorithm is at most k/(k-h+1) times the minimum possible using a cache of size h less than or equal to k. For any algorithm satisfying the latter bound, we show it is also the case that for most choices of k, the retrieval cost is either insignificant or at most a constant (independent of k) times the optimum. This helps explain why competitive ratios of many on-line paging algorithms have been typically observed to be constant in practice.

关键词： paging caching on-line algorithms competitive analysis

来源：评论

学校读者我要写书评

暂无评论

On sequential strategies for loss functions with memory

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2002年第7期48卷 1947-1958页

作者： Merhav, N Ordentlich, E Seroussi, G Weinberger, MJ Technion Israel Inst Technol Dept Elect Engn IL-32000 Haifa Israel Hewlett Packard Labs Palo Alto CA 94304 USA

The problem of optimal sequential decision for individual sequences, relative to a class of competing off-line reference strategies, is studied for general loss functions with memory. This problem is motivated by applications in which actions may have "long-term" effects, or there is a cost for switching from one action to another. As a first step, we consider the case in which the reference strategies are taken from a finite set of generic "experts." We then focus on finite-state reference strategies, assuming finite action and observation spaces. We show that key properties, that hold for finite-state strategies in the context of memoryless loss functions, do not carry over to the case of loss functions with memory. As a result, an infinite family of randomized finite-state strategies is seen to be the most appropriate reference class for this case, and the problem is basically different from its memoryless counterpart. Based on Vovk's exponential weighting technique, infinite-horizon on-line decision schemes are devised. For an arbitrary sequence of observations of length n, the excess normalized loss of these schemes relative to the best expert in a corresponding reference class is shown to be upper-bounded by an O(n(-1/3)) term in the case of a finite class, or an O([(ln n)/n](1/3)) term for the class of randomized finite-state strategies. These results parallel the O(n(-1/2)) bounds attained by previous schemes for memoryless loss functions. By letting the number of states in the reference class grow, the notion of finite-state predictability is also extended.

关键词： expert advice general loss functions on-line algorithms prediction randomized expert sequential decision

来源：评论

学校读者我要写书评

暂无评论

Competitive on-line scheduling of continuous-media streams

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2002年第2期64卷 219-248页

作者： Garofalakis, M Ioannidis, Y Özden, B Silberschatz, A Bell Labs Murray Hill NJ 07974 USA Univ Athens Dept Informat & Telecommun GR-15784 Athens Greece

Multimedia applications require a guaranteed level of service for accessing continuous-media data. To obtain such guarantees, the database server where the data are residing must employ an admission control scheme to limit the number of clients that can be served concurrently. We investigate the problem of on-line admission control, where the decision of whether to accept or reject a request must be made without any knowledge about future requests. Employing competitive analysis techniques, we address the problem in its most general form with the following key contributions: (1) We prove a tight upper bound on the competitive ratio of the conventional Work-Conserving (WC) policy, showing that it is within a factor 1+Delta/1-p of the optimal clairvoyant strategy, where Delta is the ratio of the maximum to minimum request length (i.e., time duration), and p is the maximum fraction of the server's bandwidth that a request can demand;(2) we prove a lower bound of Omega(log Delta/1-p) on the competitive ratio of any deterministic or randomized admission control scheme, demonstrating an exponential gap between greedy and optimal on-line solutions;(3) we propose simple deterministic schemes based on the idea of bandwidth prepartitioning that guarantee competitive ratios within a small constant factor of log Delta (i.e., they are provably near-optimal) if p < 1 /[log Delta];and (4) we introduce a novel admission control policy that partitions the server bandwidth based on the expected popularities of different request lengths and experimentally demonstrate its benefits compared to WC. (C) 2002 Elsevier Science (USA).

关键词： multimedia databases resource scheduling admission control on-line algorithms competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Two short notes on the on-line travelling salesman: handling times and lookahead

引用

THEORETICAL COMPUTER SCIENCE 2002年第1期289卷 845-852页

作者： Damaschke, P Chalmers Univ Technol Dept Comp Sci S-41296 Gothenburg Sweden

We study extensions of the on-line travelling salesman problem. Our results are: The optimal competitive ratio 2 for arbitrary metric spaces also holds in the case of nonzero handling times. The optimal competitive ratio 3/2 on the half-line cannot be improved by randomization, but there is a 4/3-competitive algorithm under the assumption that the server is notified when the last request has been released. This ratio is also optimal. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： on-line algorithms travelling salesman handling times lookahead

来源：评论

学校读者我要写书评

暂无评论

On-line multi-threaded paging

引用

ALGORITHMICA 2002年第1期32卷 36-60页

作者： Feuerstein, E de Loma, AS Univ Buenos Aires Fac Ciencias Exactas & Nat Dept Computat RA-1428 Buenos Aires DF Argentina

In this paper we introduce a generalization of Paging to the case where there are many threads of requests. This models situations in which the requests come from more than one independent source. Hence, apart from deciding how to serve a request, at each stage it is necessary to decide which request to serve among several possibilities. Four different on-line problems arise depending on whether we consider fairness restrictions or not, with finite or infinite input sequences. We study all of them, proving lower and upper bounds for the competitiveness of on-line algorithms. The main competitiveness results presented in this paper state that when no fairness restrictions are imposed it is possible to obtain competitive algorithms for finite and infinite inputs. On the other hand, for the fair case in general there exist no competitive algorithms. In addition, we consider three definitions of competitiveness for infinite inputs, One of them forces algorithms to behave efficiently at every finite stage, while the other two aim at comparing the algorithms' steady-state performances. A priori, the th-ree definitions seem *** study them and find, however, that they are essentially equivalent, This suggests that the competitiveness results that we obtain reflect the intrinsic difficulty of the problem and are not a consequence of a too strict definition of competitiveness.

关键词： competitive analysis fairness multi-tasking systems on-line algorithms paging

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：