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

Scheduling broadcasts with deadlines

9th Annual International Computing and Combinatorics Conference (COCOON 2003)

作者： Kim, JH Chwa, KY Pusan Natl Foreign Studies Dept Comp Engn Pusan 608738 South Korea Korea Adv Inst Sci & Technol Dept Elect Engn Comp Sci Taejon 305701 South Korea

ISBN: (纸本)3540405348

We investigate the problem of scheduling broadcasts in data delivering systems via broadcast, where a number of requests from several clients can be simultaneously satisfied by one broadcast of a server. Most of prior work has focused on minimizing the total flow time of requests. It assumes that once a request arrives, it will be held until satisfied. In this paper, we are concerned with the situation that clients may leave the system if their requests are still unsatisfied after waiting for some time, that is, each request has a deadline. The problem of maximizing the throughput, for example, the total number of satisfied requests, is developed, and there are given online algorithms achieving constant competitive ratios. (C) 2004 Elsevier B.V. All rights reserved.

关键词： broadcast scheduling on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

Competitive on-line stream merging algorithms for media-on-demand

引用

JOURNAL OF algorithms-COGNITION INFORMATICS AND LOGIC 2003年第1期48卷 59-90页

作者： Bar-Noy, A Ladner, RE CUNY Brooklyn Coll Dept Comp & Informat Sci Brooklyn NY 11210 USA Univ Washington Dept Comp Sci & Engn Seattle WA 98195 USA

We consider the problem of minimizing the bandwidth needed by media-on-demand servers that use stream merging. We consider the on-line case where client requests are not known ahead of time. To facilitate stream merging, clients have the ability to receive data from two streams simultaneously and can buffer up to half of a full stream. We present a new family of on-line stream merging algorithms called dynamic tree algorithms. The bandwidth requirements of the best of these, the dynamic Fibonacci tree algorithms, are within a factor of the minimum between log(phi)(n) + 0(l) and log(phi)(1/(2D)) + 0(l) from the off-line optimal, where n is the number of requests, D is the guaranteed maximum start-up delay measured as a fraction of the time for a full stream, and phi = (I + root5)/2. The new on-line algorithms use a dynamic Fibonacci tree to control how new arrivals should merge with existing streams. Empirical studies show that the dynamic Fibonacci tree algorithms perform much better than indicated by the analysis. (C) 2003 Elsevier Inc. All rights reserved.

关键词： video-on-demand stream merging on-line algorithms competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Competitive on-line stream merging algorithms for media-on-demand

Competitive on-line stream merging algorithms for media-on-d...

引用

12th Annual ACM-SIAM Symposium on Discrete algorithms

作者： Bar-Noy, A Ladner, RE CUNY Brooklyn Coll Dept Comp & Informat Sci Brooklyn NY 11210 USA Univ Washington Dept Comp Sci & Engn Seattle WA 98195 USA

ISBN: (纸本)0898714907

关键词： video-on-demand stream merging on-line algorithms competitive analysis

来源：评论

学校读者我要写书评

暂无评论

On-line competitive algorithms for call admission in optical networks

引用

ALGORITHMICA 2001年第1期31卷 29-43页

作者： Awerbuch, B Azar, Y Fiat, A Leonardi, S Rosén, A Johns Hopkins Univ Baltimore MD 21218 USA MIT Comp Sci Lab Cambridge MA 02139 USA Univ Roma La Sapienza Dipartimento Informat Sistemist I-00198 Rome Italy Univ Toronto Dept Comp Sci Toronto ON M5S 1A4 Canada

We study the on-line call admission problem in optical networks. We present a general technique that allows us to reduce the problem of call admission and wavelength selection to the call admission problem. We then give randomized algorithms with logarithmic competitive ratios for specific topologies in switchless and reconfigurable optical networks. We conclude by considering full duplex communications.

关键词： on-line algorithms competitive analysis optical networks

来源：评论

学校读者我要写书评

暂无评论

New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice

引用

ACM TRANSACTIONS ON COMPUTER SYSTEMS 2003年第3期21卷 270-313页

作者： Estan, C Varghese, G Univ Calif San Diego Dept Comp Sci & Engn La Jolla CA 92093 USA

Accurate network traffic measurement is required for accounting, bandwidth provisioning and detecting DoS attacks. These applications see the traffic as a collection of flows they need to measure. As link speeds and the number of flows increase, keeping a counter for each flow is too expensive ( using SRAM) or slow ( using DRAM). The current state-of-the-art methods (Cisco's sampled NetFlow), which count periodically sampled packets are slow, inaccurate and resource-intensive. Previous work showed that at different granularities a small number of "heavy hitters" accounts for a large share of traffic. Our paper introduces a paradigm shift by concentrating the measurement process on large flows only - those above some threshold such as 0.1% of the link capacity. We propose two novel and scalable algorithms for identifying the large flows: sample and hold and multistage filters, which take a constant number of memory references per packet and use a small amount of memory. If M is the available memory, we show analytically that the errors of our new algorithms are proportional to 1/M;by contrast, the error of an algorithm based on classical sampling is proportional to 1/rootM, thus providing much less accuracy for the same amount of memory. We also describe optimizations such as early removal and conservative update that further improve the accuracy of our algorithms, as measured on real traffic traces, by an order of magnitude. Our schemes allow a new form of accounting called threshold accounting in which only flows above a threshold are charged by usage while the rest are charged a fixed fee. Threshold accounting generalizes usage-based and duration based pricing.

关键词： algorithms measurement network traffic measurement usage based accounting scalability on-line algorithms identifying large flows

来源：评论

学校读者我要写书评

暂无评论

On-line grid-packing with a single active grid

引用

INFORMATION PROCESSING LETTERS 2003年第4期85卷 199-204页

作者： Fujita, S Hiroshima Univ Grad Sch Engn Dept Informat Engn Higashihiroshima 7398527 Japan

In this paper, we study the problem of packing rectangular items into a minimum number of square grids in an on-line manner with a single active grid, where the size of each grid is m x m for some positive integer m, and the height and the width of each item are positive integers smaller than or equal to m, respectively. We prove two elementary bounds on the asymptotic competitive ratio of an optimal on-line algorithm, that is at least 23/11 and at most (4/3) rootm - o(rootm). We then propose an on-line algorithm that achieves a competitive ratio 0((log log m)(2)). (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： on-line algorithms grid-packing bounds

来源：评论

学校读者我要写书评

暂无评论

On-line edge-coloring with a fixed number of colors

引用

ALGORITHMICA 2003年第2期35卷 176-191页

作者： Favrholdt, LM Nielsen, MN Department of Mathematics and Computer Science University of Southern Denmark Campusvej 55 DK-5230 Odense M Denmark. lenem@imada.sdu.dk nyhave@imada.sdu.dk. DK

We investigate a variant of on-line edge-coloring in which there is a fixed number of colors available and the aim is to color as many edges as possible. We prove upper and lower bounds on the performance of different. classes of algorithms for the problem. Moreover, we determine the performance of two specific algorithms, First-Fit and Next-Fit. Specifically, algorithms that never reject edges that they are able to color are called fair algorithms. We consider the four combinations of fair/not fair and deterministic/randomized. We show that the competitive ratio of deterministic fair algorithms can vary only between approximately 0.4641 and (1)/(2), and that Next-Fit is worst possible among fair algorithms. Moreover, we show that no algorithm is better than (4)/(7)-competitive. If the graphs are all k-colorable, any fair algorithm is at least (1)/(2)-competitive. Again, this performance is matched by Next-Fit while the competitive ratio for First-Fit is shown to be k/(2k - 1), which is significantly better, as long as k is not too large.

关键词： edge-coloring on-line algorithms competitive analysis fixed number of colors maximization problem fair algorithms k-colorable graphs accommodating sequences restricted adversary randomization

来源：评论

学校读者我要写书评

暂无评论

Dynamic TCP acknowledgment in the LogP model

引用

JOURNAL OF algorithms-COGNITION INFORMATICS AND LOGIC 2003年第2期48卷 407-428页

作者： Frederiksen, JS Larsen, KS Noga, J Uthaisombut, P Univ So Denmark Dept Math & Comp Sci Odense Denmark Calif State Univ Northridge Dept Comp Sci Northridge CA 91330 USA Univ Pittsburgh Dept Comp Sci Pittsburgh PA 15260 USA

When messages, which are to be sent point-to-point in a network, become available at irregular intervals, a decision must be made each time a new message becomes available as to whether it should be sent immediately or if it is better to wait for more messages and send them all together. Because of physical properties of the networks, a certain minimum amount of time must elapse in between the transmission of two packets. Thus, whereas waiting delays the transmission of the current data, sending immediately may delay the transmission of the next data to become available even more. We propose a new quality measure and derive optimal deterministic and randomized algorithms for this on-line problem. (C) 2003 Elsevier Inc. All rights reserved.

关键词： dynamic TCP acknowledgment packet bundling on-line algorithms competitive ratio flow-time deterministic randomized

来源：评论

学校读者我要写书评

暂无评论

Tight bounds on the competitive ratio on accommodating sequences for the seat reservation problem

引用

JOURNAL OF SCHEDULING 2003年第2期6卷 131-147页

作者： Bach, E Boyar, J Epstein, L Favrholdt, LM Jiang, T Larsen, KS Lin, GH Van Stee, R Odense Univ Univ So Denmark Dept Math & Comp Sci DK-5230 Odense M Denmark Univ Wisconsin Dept Comp Sci Madison WI 53706 USA Interdisciplinary Ctr Sch Comp & Media Sci IL-46150 Herzliyya Israel Univ Calif Riverside Dept Comp Sci Riverside CA 92521 USA Univ Waterloo Dept Comp Sci Waterloo ON N2L 3G1 Canada McMaster Univ Dept Comp & Software Hamilton ON L8S 4L8 Canada CWI Ctr Math & Comp Sci NL-1090 GB Amsterdam Netherlands

The unit price seat reservation problem is investigated. The seat reservation problem is the problem of assigning seat numbers on-line to requests for reservations in a train traveling through k stations. We are considering the version where all tickets have the same price and where requests are treated fairly, that is, a request which can be fulfilled must be granted. For fair deterministic algorithms, we provide an asymptotically matching upper bound to the existing lower bound which states that all fair algorithms for this problem are (1)/(2) competitive on accommodating sequences, when there are at least three seats. Additionally, we give an asymptotic upper bound of (7)/(9) for fair randomized algorithms against oblivious adversaries. We also examine concrete on-line algorithms, First-Fit and Random for the special case of two seats. Tight analyses of their performance are given.

关键词： competitive ratio accomodating sequences on-line algorithms seat reservation problem

来源：评论

学校读者我要写书评

暂无评论

On-line multi-threaded scheduling

引用

JOURNAL OF SCHEDULING 2003年第2期6卷 167-181页

作者： Feuerstein, E Mydlarz, M Stougie, L Univ Buenos Aires Fac Ciencias Exactas & Nat Dept Computat RA-1053 Buenos Aires DF Argentina Rutgers State Univ Dept Comp Sci Piscataway NJ 08854 USA Tech Univ Eindhoven Fac Math Combinatorial Optimizat Grp NL-5600 MB Eindhoven Netherlands Ctr Math & Comp Sci CWI NL-1090 GB Amsterdam Netherlands

On-line scheduling problems are studied with jobs organized in a number of sequences called threads. Each job becomes available as soon as a scheduling decision is made on all preceding jobs in the same thread. We consider two different on-line paradigms. The first one models a sort of batch process: a schedule is constructed, in an on-line way, which is to be executed later. The other one models a real-time planning situation: jobs are immediately executed at the moment they are assigned to a machine. The classical objective functions of minimizing makespan and minimizing average completion time of the jobs are studied. We establish a fairly complete set of results for these problems. One of the highlights is that List Scheduling is a best possible algorithm for the makespan problem under the real-time model if the number of machines does not exceed the number of threads by more than 1. Another one is a polynomial time best possible algorithm for minimizing the average completion time on a single machine under both on-line paradigms.

关键词： on-line algorithms multiple threads competitive analysis scheduling problems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：