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

on-line algorithms for the dominating set problem

INFORMATION PROCESSING LETTERS 1997年第1期61卷 11-14页

作者： King, GH Tzeng, WG NATL CHIAO TUNG UNIV DEPT COMP & INFORMAT SCIHSINCHU 30050TAIWAN

The online version of the dominating set problem is considered in 2 settings. The first setting is that all vertices 1, 2, ..., n in the graph are given in advance. At time interval i the adjacency condition of vertex i to the other vertices is presented. An online algorithm of performance ratio 1.5 square root of n + c-sub-1 is proposed and it is shown that the square root n - c-sub-2 is a lower bound for the performance ratio that an online dominating set algorithm can possibly achieve, where c-sub-1 and c-sub-2 are some positive constants.

关键词： algorithms on-line algorithms dominating set

来源：评论

学校读者我要写书评

暂无评论

Semi on-line algorithms for the partition problem

引用

OPERATIONS RESEARCH LETTERS 1997年第5期21卷 235-242页

作者： Kellerer, H Kotov, V Speranza, MC Tuza, Z Graz Univ Inst Stat Okonometrie & Operat Res A-8010 Graz Austria Univ Minsk Fac Appl Math & Comp Sci Minsk 220080 BELARUS Univ Brescia Dipartimento Metodi Quantitat Fac Econ & Commercio I-25122 Brescia Italy Hungarian Acad Sci Inst Comp & Automat H-1111 Budapest Hungary

The partition problem is one of the basic NP-complete problems. While an efficient heuristic for the optimization version, which is equivalent to minimizing the makespan on two identical machines, is known with worst-case ratio 12/11, no deterministic heuristic for the on-line problem can have a worst-case ratio lower than 3/2 In this paper we investigate three different semi on-line versions of the partition problem. In the first case, we assume that a buffer of length k is available to maintain k items. In the second case, two parallel processors are available which assign each item independently to the partition sets. The best of the two produced solutions is chosen. Finally, in the third problem the total sum of the items is known in advance. For each version we propose a heuristic and investigate its worst-case ratio. All algorithms have a worst-case ratio of which is shown to be the best possible worst-case ratio. (C) 1997 Elsevier Science B.V. All rights reserved.

关键词： partition scheduling on-line algorithms worst-case ratio

来源：评论

学校读者我要写书评

暂无评论

LRU is better than FIFO

引用

ALGORITHMICA 1999年第2期23卷 180-185页

作者： Chrobak, M Noga, J Univ Calif Riverside Dept Comp Sci Riverside CA 92521 USA Univ Calif Riverside Dept Math Riverside CA 92521 USA

In the paging problem we have to manage a two-level memory system, in which the first level has short access time but can hold only up to k pages, while the second level is very large but slow. We use competitive analysis to study the relative performance of the two best known algorithms for paging, LRU and FIFO. Sleator and Tarjan proved that the competitive ratio of LRU and FIFO is k. In practice, however, LRU is known to perform much better than FIFO. It is believed that the superiority of LRU can be attributed to locality of reference exhibited in request sequences. In order to study this phenomenon, Borodin et al. [2] refined the competitive approach by introducing the concept of access graphs. They conjectured that the competitive ratio of LRU on each access graph is less than or equal to the competitive ratio of FIFO. We prove this conjecture in this paper.

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

来源：评论

学校读者我要写书评

暂无评论

Improved bounds for on-line load balancing

引用

ALGORITHMICA 1999年第4期23卷 278-301页

作者： Andrews, M Goemans, MX Zhang, L MIT Dept Math Cambridge MA 02139 USA

We consider the following load balancing problem. Jobs arrive on-line and must be assigned to one of m machines thereby increasing the load on that machine by a certain weight. Jobs also depart on-line. The goal is to minimize the maximum load on any machine, the load being defined as the sum of the weights of the jobs assigned to the machine divided by the machine capacity. The scheduler also has the option of preempting a job and reassigning it to another machine. Whenever a job is assigned or reassigned to a machine, the on-line algorithm incurs a reassignment cost depending on the job. For arbitrary reassignment costs and identical machines, we present an on-line algorithm with a competitive ratio of 3.5981 against current load, i.e., the maximum load at any time is less than 3.5981 times the lowest achievable load at that time. Our algorithm also incurs a reassignment cost less than 6.8285 times the cost of assigning all the jobs. For arbitrary reassignment costs and related machines we present an algorithm with a competitive ratio of 32 and a reassignment factor of 79.4. We also describe algorithms with better performance guarantees for some special cases of the problem.

关键词： load balancing on-line algorithms competitive analysis current load

来源：评论

学校读者我要写书评

暂无评论

Balanced allocations

引用

SIAM JOURNAL ON COMPUTING 1999年第1期29卷 180-200页

作者： Azar, Y Broder, AZ Karlin, AR Upfal, E Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel Digital Syst Res Ctr Palo Alto CA 94301 USA Univ Washington Dept Comp Sci Seattle WA 98195 USA IBM Corp Almaden Res Ctr San Jose CA 95120 USA Weizmann Inst Sci Dept Appl Math IL-76100 Rehovot Israel

Suppose that we sequentially place n balls into n boxes by putting each ball into a randomly chosen box. It is well known that when we are done, the fullest box has with high probability (1 + o(1)) ln n/ ln ln n balls in it. Suppose instead that for each ball we choose two boxes at random and place the ball into the one which is less full at the time of placement. We show that with high probability, the fullest box contains only ln ln n/ ln 2 + O(1) balls-exponentially less than before. Furthermore, we show that a similar gap exists in the infinite process, where at each step one ball, chosen uniformly at random, is deleted, and one ball is added in the manner above. We discuss consequences of this and related theorems for dynamic resource allocation, hashing, and on-line load balancing.

关键词： urn models occupancy problems on-line algorithms resource allocation hashing load balancing

来源：评论

学校读者我要写书评

暂无评论

Adaptive disk spindown via optimal rent-to-buy in probabilistic environments

引用

ALGORITHMICA 1999年第1期23卷 31-56页

作者： Krishnan, P Long, PM Vitter, JS AT&T Bell Labs Holmdel NJ 07733 USA Natl Univ Singapore ISCS Dept Singapore 119260 Singapore Duke Univ Dept Comp Sci Durham NC 27708 USA

In the single rent-to-buy decision problem, without a priori knowledge of the amount of time a resource will be used we need to decide when to buy the resource, given that we can rent the resource for $1 per unit time or buy it once and for all for $c. In this paper we study algorithms that make a sequence of single rent-to-buy decisions, using the assumption that the resource use times are independently drawn from an unknown probability distribution. Our study of this rent-to-buy problem is motivated by important systems applications, specifically, problems arising from deciding when to spindown disks to conserve energy in mobile computers [4], [13], [15], thread blocking decisions during lock acquisition in multiprocessor applications [7], and virtual circuit holding times in IP-over-ATM networks [11], [19]. We develop a provably optimal and computationally efficient algorithm for the rent-to-buy problem. Our algorithm uses O (root t) time and space, and its expected cost for the tth resource use converges to optimal as O (root logt/t), for any bounded probability distribution on the resource use times. Alternatively, using O(1) time and space, the algorithm almost converges to optimal. We describe the experimental results for the application of our algorithm to one of the motivating systems problems: the question of when to spindown a disk to save power in a mobile computer. Simulations using disk access traces obtained from an HP workstation environment suggest that our algorithm yields significantly improved power/response time performance over the nonadaptive 2-competitive algorithm which is optimal in the worst-case competitive analysis model.

关键词： mobile computing on-line algorithms machine learning power conservation disk spindown rent-to-buy multiprocessor spin/block IP-over-ATM virtual circuit holding time

来源：评论

学校读者我要写书评

暂无评论

Exploring an unknown graph

引用

JOURNAL OF GRAPH THEORY 1999年第3期32卷 265-297页

作者： Deng, XT Papadimitriou, CH City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong SAR Peoples R China Univ Calif Berkeley Dept Comp Sci & Engn Berkeley CA 94720 USA

We wish to explore all edges of an unknown directed, strongly connected graph. At each point, we have a map of ail nodes and edges we have visited, we can recognize these nodes and edges if we see them again, and we know how many unexplored edges emanate from each node we have visited, but we cannot tell where each leads until we traverse it. We wish to minimize the ratio of the total number of edges traversed divided by the optimum number of traversals, had we known the graph. For Eulerian graphs, this ratio cannot be better than two, and two is achievable by a simple algorithm. In contrast, the ratio is unbounded when the deficiency of the graph (the number of edges that have to be added to make it Eulerian) is unbounded. Our main result is an algorithm that achieves a bounded ratio when the deficiency is bounded. (C) 1999 John Wiley & Sons, Inc.

关键词： graphs directed graphs search on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for partitioning small items in unequal bins to minimize the total size

引用

DISCRETE APPLIED MATHEMATICS 1999年第1-3期94卷 181-191页

作者： Dell'Olmo, P Speranza, MG Univ Brescia Dept Quantitat Methods I-25122 Brescia Italy Univ Roma Tor Vergata Dept Comp Sci Syst & Prod I-00133 Rome Italy

A set of items has to be assigned to a set of bins with different sizes, If necessary the size of each bin can be extended. The objective is to minimize the total size, i.e. the sum of the sizes of the bins. In this paper we study both the off-line case and the on-line variant of this problem under the assumption that each item is smaller than any bin. For the former case, when all times are known in advance, we analyze the worst-case performance of the longest processing time heuristic and prove a bound of 2(2 - root 2). For the on-line case, where each incoming item has to be assigned immediately to a bin and the assignment cannot be changed later, we give a lower bound of 7/6 on the worst-case relative error of any on-line algorithm with respect to the off-line problem and we show that a list scheduling algorithm, which assigns the incoming item to the bin with biggest idle space, has a worst-case performance ratio equal to 5/4. This bound is shown to be tight. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： bin-packing multiprocessor scheduling approximation on-line algorithms worst-case performance

来源：评论

学校读者我要写书评

暂无评论

On-line difference maximization

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 1999年第1期12卷 78-90页

作者： Kao, MY Tate, SR Yale Univ Dept Comp Sci New Haven CT 06520 USA Univ N Texas Dept Comp Sci Denton TX 76208 USA

In this paper we examine problems motivated by on-line financial problems and stochastic games. In particular, we consider a sequence of entirely arbitrary distinct values arriving in random order, and must devise strategies for selecting low values followed by high values in such a way as to maximize the expected gain in rank from low values to high values. First, we consider a scenario in which only one low value and one high value may be selected. We give an optimal on-line algorithm for this scenario, and analyze it to show that, surprisingly, the expected gain is n - O(1), and so differs from the best possible off-line gain by only a constant additive term (which is, in fact, fairly small-at most 15). In a second scenario, we allow multiple nonoverlapping low/high selections, where the total gain for our algorithm is the sum of the individual pair gains. We also give an optimal on-line algorithm for this problem, where the expected gain is n(2)/8 - Theta(n log n). An analysis shows that the optimal expected off-line gain is n(2)/6 + Theta(1), so the performance of our on-line algorithm is within a factor of 3/4 of the best off-line strategy.

关键词： analysis of algorithms on-line algorithms financial games secretary problem

来源：评论

学校读者我要写书评

暂无评论

The seat reservation problem

引用

ALGORITHMICA 1999年第4期25卷 403-417页

作者： Boyar, J Larsen, KS Odense Univ Dept Math & Comp Sci DK-5230 Odense M Denmark

We investigate the problem of giving seat reservations on-line. We assume that a train travels from a start station to an end station, stopping at k stations, including the first and last. Reservations can be made for any trip going from any station to any later station. The train has a fixed number of seats. The seat reservation system attempts to maximize income. We consider the case in which all tickets have the same price and the case in which the price of a ticket is proportional to the length of the trip. For both cases we prove upper and lower bounds of Theta (1/k) on the competitive ratio of any "fair" deterministic algorithm. We also define the accommodating ratio which is similar to the competitive ratio except that the only sequences of requests allowed are sequences for which the optimal off-line algorithm could accommodate all requests. We prove upper and lower bounds of Theta (1) on the accommodating ratio of any "fair" deterministic algorithm, in the case in which all tickets have the same price, but Theta (1/k) in the case in which the ticket price is proportional to the length of the trip. The most surprising of these results is that all "fair" algorithms are at least 1/2-accommodating when all tickets have the same price. We prove similar results bounding the performance of any "fair" randomized algorithm against an adaptive on-line adversary. We also consider concrete algorithms;more specifically, First-Fit and Best-Fit.

关键词： on-line algorithms competitive ratio accommodating ratio graph coloring interval graphs seat reservation problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：