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

On-line scheduling with forbidden zones

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY 2007年第1期58卷 80-90页

作者： Khammuang, K. Abdekhodaee, A. Wirth, A. Univ Melbourne Dept Mech & Mfg Engn Melbourne Vic 3010 Australia

In various manufacturing and computing contexts there may be a certain period in each time interval, during which processing may continue but may not be initiated. We examine the problem of on-line scheduling in the presence of such forbidden zones, whose complements are starting time windows. We show that no on-line algorithm is better than (9)/(7)-competitive, when minimizing the number of intervals used (essentially the makespan), whereas list scheduling is shown to be 2-competitive. We also investigate adaptations of the first fit, next fit and harmonic bin packing algorithms and test all four empirically.

关键词： scheduling on-line algorithms competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Dynamic Shannon coding

引用

INFORMATION PROCESSING LETTERS 2007年第2-3期102卷 113-117页

作者： Gagie, Travis Univ Toronto Dept Comp Sci Toronto ON Canada

We present the first algorithm for one-pass instantaneous coding which, given l > 0 and a string S of length m over an alphabet of size n, is guaranteed to encode S using at most (H + 1 + (1/(2l - 1)ln2)m + O(n log m) bits (H denotes the Oth-order empirical entropy of S), a proportional length of time, and no codewords longer than log n + f + 1 bits. (c) 2006 Elsevier B.V. All rights reserved.

关键词： data compression on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimal resource augmentations for online knapsack

引用

10th Int Workshop on Approximation algorithms for Combinatorial Optimization Problems/11th Int Workshop on Randomization and Computation

作者： Iwama, Kazuo Zhang, Guochuan Kyoto Univ Sch Informat Kyoto Japan Zhejiang Univ Dept Math Hangzhou Peoples R China

ISBN: (纸本)9783540742074

It is known that online knapsack is not competitive. This negative result remains true even if the items are removable. In this paper we consider online removable knapsack with resource augmentation, in which we hold a knapsack of capacity R >= 1.0 and aim at maintaining a feasible packing to maximize the total weight of the items packed. Accepted items can be removed to leave room for newly arriving items. Once an item is rejected/removed it can not be considered again. We evaluate an online algorithm by comparing the resulting packing to an optimal packing that uses a knapsack of capacity one. Optimal online algorithms are derived for both the weighted case (items have arbitrary weights) and the un-weighted case (the weight of an item is equal to its size).

关键词： on-line algorithms knapsack resource augmentation

来源：评论

学校读者我要写书评

暂无评论

Work function algorithm with a moving window for solving the on-line k-server problem

Work function algorithm with a moving window for solving the...

引用

29th International Conference on Information Technology Interfaces

作者： Baumgartner, Alfonzo Manger, Robert Hocenski, Zeljko Univ Osijek Fac Elect Engn Kneza Troimira 2B Osijek 31000 Croatia Univ Zagreb Dept Math Zagreb 10000 Croatia

ISBN: (纸本)9789537138097

We consider a modification of the well known work function algorithm (WFA) for solving the on-line k-server problem. Our modified WFA is based on a moving window, i.e. on the approximate work function that takes into account only a fixed number of most recent on-line requests. The main motivation for using a moving window is to gain control over the prohibitive computational complexity imposed by the original algorithm. Experimental results are presented, where the performance of the modified WFA has been compared vs. the original WFA.

关键词： on-line problems on-line algorithms the k-server problem the work function algorithm (WFA) moving windows experiments

来源：评论

学校读者我要写书评

暂无评论

Online Frequency Allocation in Cellular Networks 07

Online Frequency Allocation in Cellular Networks

引用

19th Annual Symposium on Parallelism in algorithms and Architectures

作者： Chan, Joseph Wun-Tat Chin, Francis Y. L. Ye, Deshi Zhang, Yong Kings Coll London Dept Comp Sci London WC2R 2LS England

ISBN: (纸本)9781595936677

Given a mobile telephone network, whose geographical coverage area, is divided into cells, phone calls are serviced by assigning frequencies to them, so that no two calls emanating from the same or neighboring cells are assigned the same frequency. Assuming an online arrival of calls and the calls will not terminate, the problem is to minimize the span of frequencies used. By first, considering chi-colorable networks, which is a generalization of (the 3-colorable) cellular networks, we present a (chi + 1)/2-competitive online algorithm. This algorithm, when applied to cellular networks, is effectively a positive solution to the open problem posed in [8]: Does a 2-competitive online algorithm exist for frequency allocation in cellular networks? We further prove a lower bound which shows that our 2-competitive algorithm is optimal. We discover that an interesting phenomenon occurs for the online frequency allocation problem when the number of calls considered becomes large: previously-derived optimal (lower and upper) bounds on competitive ratios no longer hold true. For cellular networks, we show new asymptotic lower and upper bounds of 1.5 and 1.9126, respectively, which breaks through the optimal bound of 2 shown previously.

关键词： on-line algorithms Frequency allocation Competitive analysis Cellular networks

来源：评论

学校读者我要写书评

暂无评论

Load Balancing for Typical Radar Systems with Overlapping Surveillance Space

Load Balancing for Typical Radar Systems with Overlapping Su...

引用

IET International Conference on Radar Systems (Radar 2007)

作者： Jian-Jia Chen Chin-Fu Kuo Department of Computer Science and Information Engineering National Taiwan University Taiwan Department of Computer Science and Information Engineering National University of Kaohsiung Taiwan

Dwell scheduling has been an important issue for radar systems. This research explores the on-line dwell scheduling issue over multiple transmitters/receivers in radar systems. We investigate the minimization of the maximum load in the system to balance workloads over multiple transmitters/receivers. Two on-line algorithms are proposed and analyzed against adversaries. Algorithm GREEDY, which assigns an incoming dwell task to the available transmitters/receivers, is shown to be a 3-competitive algorithm against the adversary. The online algorithm, denoted by Algorithm FIXED, by assigning the arriving dwell task to a pre-defined transmitters/receivers is proved to be a 2-competitive algorithm. The capability of the proposed algorithms is evaluated by a series of experiments. Although Algorithm FIXED outperforms Algorithm GREEDY against adversaries in the worst cases, Algorithm GREEDY outperforms Algorithm FIXED if the dwell tasks are uniformly distributed in the behavior in experiments.

关键词： Load balance Overlapping surveillance space Radar systems on-line algorithms Competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Dial-a-Ride Problem with Time-Windows and on-line algorithms

Dial-a-Ride Problem with Time-Windows and On-Line Algorithms

引用

中国运筹学会第七届学术交流会

作者： Yi Fanglei Xu Yinfeng School of Management,Xi'an Jiaotong University, Xi'an, 710049

In this paper results on dial-a-ride problem with time-windows are pre-sented. Requests for rides appearing over time consist of two points in a metric space,a source and a *** transport objects of requests from sources to des-tinations. Each request specifies a deadlines. If a request is not be served by itsdeadline, it will be called *** goal is to plan the motion of servers in an on-lineway so that the maximum number of requests is met by their deadline. We performcompetitive analysis of two deterministic strategies for the problem in two cases sep-arately, when the server has finite capacity (z=1) and when the server has infinitecapacity (z =∞). Then we obtain their competitive ratios.

关键词： Logistics Vehicle Scheduling on-line algorithms Competitive Analysis

来源：评论

学校读者我要写书评

暂无评论

The generalized two-server problem

引用

JOURNAL OF THE ACM 2006年第3期53卷 437-458页

作者： Sitters, Rene A. Stougie, Leen Max Planck Inst Informat D-66123 Saarbrucken Germany Tech Univ Eindhoven NL-5600 MB Eindhoven Netherlands Ctr Wiskunde & Informat NL-1090 GB Amsterdam Netherlands

We consider the generalized on-line two-server problem in which each server moves in its own metric space. Requests for service arrive one-by-one and every request is represented by two points: one in each metric space. The problem is to move, at every request, one of the two servers to its request-point such that the total distance travelled by the two servers is minimized. The special case in which both metric spaces are the real line is known as the CNN-problem. It has been a well-known open question in on-line optimization if an algorithm with a constant-competitive ratio exists for this problem. We answer this question in the affirmative by providing a constant-competitive algorithm for the generalized two-server problem on any metric space. The basic result in this article is a characterization of competitiveness for metrical service systems that seems much easier to use when looking for a competitive algorithm. The existence of a competitive algorithm for the generalized two-server problem follows rather easily from this result.

关键词： algorithms theory work function metrical service system kappa-server problem on-line algorithms competitive analysis

来源：评论

学校读者我要写书评

暂无评论

The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates

引用

MATHEMATICAL PROGRAMMING 2006年第1期106卷 137-157页

作者： Chou, MC Queyranne, M Simchi-Levi, D Natl Univ Singapore Dept Decis Sci Singapore 117548 Singapore Univ British Columbia Fac Commerce & Business Adm Vancouver BC V5Z 1M9 Canada MIT Dept Civil & Environm Engn Cambridge MA 02139 USA

Jobs arriving over time must be non-preemptively processed on one of m parallel machines, each running at its own speed, so as to minimize a weighted sum of the job completion times. In this on-line environment, the processing requirement and weight of a job are not known before the job arrives. The Weighted Shortest Processing Requirement (WSPR) heuristic is a simple extension of the well known WSPT heuristic, which is optimal for the single machine problem without release dates. According to WSPR, whenever a machine completes a job, the next job assigned to it is the one with the least ratio of processing requirement to weight among all jobs available for processing at this point in time. We analyze the performance of this heuristic and prove that its asymptotic competitive ratio is one for all instances with bounded job processing requirements and weights. This implies that the WSPR algorithm generates a solution whose relative error approaches zero as the number of jobs increases. Our proof does not require any probabilistic assumption on the job parameters and relies extensively on properties of optimal solutions to a single machine relaxation of the problem.

关键词： scheduling Asymptotic Performance Ratio on-line algorithms Analysis of Heuristics

来源：评论

学校读者我要写书评

暂无评论

The traveling miser problem

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2006年第4期14卷 711-724页

作者： Breitgand, David Raz, Danny Shavitt, Yuval Univ Haifa IBM Haifa Res Lab IL-31905 Haifa Israel Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel Tel Aviv Univ Sch Elect Engn IL-69978 Tel Aviv Israel

Various monitoring and performance evaluation tools generate considerable amount of low priority traffic. This information is not always needed in real time and often can be delayed by the network without hurting functionality. This paper proposes a new framework to handle this low priority, but resource consuming traffic in such a way that it incurs a minimal interference with the higher priority traffic. Consequently, this improves the network goodput. The key idea is allowing the network nodes to delay data by locally storing it This can be done, for example, in the Active Network paradigm. In this paper we show that such a model can improve the network's goodput dramatically even if a very simple scheduling algorithm for intermediate parking is used. The parking imposes additional load on the intermediate nodes. To obtain minimal cost schedules we define an optimization problem called the traveling miser problem. We concentrate on the on-line version of the problem for a predefined route, and develop a number of enhanced scheduling strategies. We study their characteristics under different assumptions on the environment through a rigorous simulation study. We prove that if only one link can be congested, then our scheduling algorithm is O(log(2)B) competitive, where B is congestion time, and is 3-competitive, if additional signaling is allowed.

关键词： active networks competitive analysis delay tolerant networks network management on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：