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

ALGORITHMICA 1999年第1期25卷 22-36页

作者： Azar, Y Bartal, Y Feuerstein, E Fiat, A Leonardi, S Rosén, A Tel Aviv Univ Dept Comp Sci Ramat Aviv Israel Int Comp Sci Inst Berkeley CA 94704 USA Univ Buenos Aires Fac Ciencias Exactas & Nat Dept Computac Buenos Aires DF Argentina Univ Gen Sarmiento Inst Ciencias Gen Sarmiento Argentina Univ Rome La Sapienza Dipartimento Informat Sistemist Rome Italy Univ Toronto Dept Comp Sci Toronto ON Canada

We deal with the problem of making capital investments in machines for manufacturing a product. Opportunities for investment occur over time, every such option consists of a capital cost for a new machine and a resulting productivity gain, i.e., a lower production cost for one unit of product. The goal is that of minimizing the total production costs and capital costs when future demand for the product being produced and investment opportunities are unknown. This can be viewed as a generalization of the ski-rental problem and related to the mortgage problem [3]. If all possible capital investments obey the rule that lower production costs require higher capital investments, then we present an algorithm with constant competitive ratio. If new opportunities may be strictly superior to previous ones (in terms of both capital cost and production cost), then we give an algorithm which is O(min {l + log C, 1 + log log P, 1 + log M}) competitive, where C is the ratio between the highest and the lowest capital costs, P is the ratio between the highest and the lowest production costs, and M is the number of investment opportunities. We also present a lower bound on the competitive ratio of any on-line algorithm for this case, which is Omega (min{log C, log log P/ log log log P, log M/ log log M}). This shows that the competitive ratio of our algorithm is tight (up to constant factors) as a function of C, and not far from the best achievable as a function of P and M.

关键词： on-line algorithms competitive ratio on-line financial problems

来源：评论

学校读者我要写书评

暂无评论

Competitive optimal on-line leasing

引用

ALGORITHMICA 1999年第1期25卷 116-140页

作者： El-Yaniv, R Kaniel, R Linial, N Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel Univ Penn Wharton Business Sch Philadelphia PA 19104 USA Hebrew Univ Jerusalem Inst Comp Sci IL-91904 Jerusalem Israel

Consider an on-line player who needs same equipment (e.g., a computer) for an initially unknown number of periods. At the start of each period it is determined whether the player will need the equipment during the current period and the player has two options: to pay a leasing fee c and rent the equipment for the period, or to buy it for a larger amount P. The total cost incurred by the player is the sum of all leasing fees and perhaps one purchase. The above problem, called the leasing problem (in computer science folklore it is known as the ski-rental problem), has received considerable attention in the economic literature. Using the competitive ratio as a performance measure this paper is concerned with determining the optimal competitive on-line policy for the leasing problem. For the simplest version of the leasing problem (as described above) it is known and readily derived that the optimal deterministic competitive performance is achieved by leasing for the first k - 1 times and then buying, where k = P/c. This strategy Days at most 2 - l/k times the optimal off-line cost. When considering alternative financial transactions one must consider their net present value. Thus, accounting for the interest rate is an essential feature of any reasonable financial model. In this paper we determine both deterministic and randomized optimal on-line leasing strategies while accounting for the interest rate factor. It is shown here, for the leasing problem, that the interest rate factor reduces the uncertainty involved. We Rnd that the optimal deterministic competitive ratio is 1 + (1 + i)(l - l/k)(l - k(i/l + i)), a decreasing function of the interest i (for all reasonable values of i). For some applications, realistic values of interest rates result in relatively low competitive ratios. By using randomization the on-line player can further boost up the performance. In particular, against an oblivious adversary the on-line player can attain a strictly smaller competitive

关键词： leasing lease-or-buy problem on-line algorithms competitive analysis equipment rental ski rental

来源：评论

学校读者我要写书评

暂无评论

A risk-reward framework for the competitive analysis of financial games

引用

ALGORITHMICA 1999年第1期25卷 99-115页

作者： al-Binali, S Columbia Univ Dept Comp Sci New York NY 10027 USA

Competitive analysis is concerned with minimizing a relative measure of performance. When applied to financial trading strategies, competitive analysis leads to the development of strategies with minimum relative performance risk. This approach is too inflexible. Many investors are interested in managing their risk: they may be willing to increase their risk for some form of reward. They may also have some forecast of the future. In this paper we extend competitive analysis to provide a framework in which investors can develop optimal trading strategies based on their risk tolerance and forecast. We first define notions of risk and reward that are natural extensions of classical competitive analysis and then illustrate our ideas using the ski-rental problem. Finally, we analyze a financial game using the risk-reward framework, and, in particular, derive an optimal risk-tolerant algorithm.

关键词： adaptive trading strategies competitive analysis forecast on-line algorithms reward risk

来源：评论

学校读者我要写书评

暂无评论

On-line resource management with application to routing and scheduling

引用

ALGORITHMICA 1999年第1期24卷 29-49页

作者： Leonardi, S Marchetti-Spaccamela, A Univ Rome La Sapienza Dipartimento Informat & Sistemist I-00198 Rome Italy

We propose a framework to model on-line resource management problems based on an on-line version of positive linear programming. We consider both min cost problems and max benefit problems and propose logarithmic competitive algorithms that are optimal up to a constant factor. The proposed framework provides a general methodology that applies to a wide class of on-line problems: shop scheduling, packet routing, and in general a class of packing and assignment problems. Previously studied problems as on-line multiprocessor scheduling and on-line virtual circuit routing can also be modeled within this framework.

关键词： on-line algorithms competitive analysis routing scheduling linear programming

来源：评论

学校读者我要写书评

暂无评论

Average case analyses of list update algorithms, with applications to data compression

引用

ALGORITHMICA 1998年第3期21卷 312-318页

作者： Albers, S Mitzenmacher, M Max Planck Inst Informat D-66123 Saarbrucken Germany Digital Equipment Corp Syst Res Ctr Palo Alto CA 94301 USA

We study the performance of the Timestamp (0) (TS(0)) algorithm for self-organizing sequential search on discrete memoryless sources. We demonstrate that TS(0) is better than Move-to-front on such sources, and determine performance ratios for TS(0) against the optimal off-line and static adversaries in this situation. Previous work on such sources compared on-line algorithms only with static adversaries. One practical motivation for our work is the use of the Move-to-front heuristic in various compression algorithms. Our theoretical results suggest that in many cases using TS(0) in place of Move-to-front in schemes that use the latter should improve compression. Tests using implementations on a standard corpus of test documents demonstrate that TS(0) leads to improved compression.

关键词： on-line algorithms competitive analysis list update problem probability distribution data compression entropy

来源：评论

学校读者我要写书评

暂无评论

Scheduling uniform machines on-line requires nondecreasing speed ratios

引用

MATHEMATICAL PROGRAMMING 1998年第1-2期82卷 225-234页

作者： Vestjens, APA Eindhoven Univ Technol Dept Math & Comp Sci NL-5600 MB Eindhoven Netherlands

We consider the following on-line scheduling problem. We have to schedule n independent jobs, where n is unknown, on m uniform parallel machines so as to minimize the makespan;preemption is allowed. Each job becomes available at its release date, and this release date is not known beforehand;its processing requirement becomes known at its arrival. We show that if only a finite number of preemptions is allowed, there exists an algorithm that solves the problem if and only if s(i-1)/s(i) less than or equal to s(i)/s(i+1) for all i = 2,..., m - 1, where s(i) denotes the ith largest machine speed. We also show that if this condition is satisfied, then Ci(mn) preemptions are necessary, and we provide an example to show that this bound is tight. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

关键词： on-line algorithms preemptive scheduling uniform machines

来源：评论

学校读者我要写书评

暂无评论

Dynamic trees and dynamic point location

引用

SIAM JOURNAL ON COMPUTING 1998年第2期28卷 612-636页

作者： Goodrich, MT Tamassia, R Johns Hopkins Univ Dept Comp Sci Baltimore MD 21218 USA Brown Univ Dept Comp Sci Providence RI 02912 USA

This paper describes new methods for maintaining a point-location data structure for a dynamically changing monotone subdivision. The main approach is based on the maintenance of two interlaced spanning trees, one for and one S for the graph-theoretic planar dual of. Queries are answered by using a centroid decomposition S of the dual tree to drive searches in the S primal tree. These trees are maintained via the link-cut trees structure of Sleator and Tarjan [J. Comput. System Sci., 26 (1983), pp. 362-381], leading to a scheme that achieves vertex insertion/deletion in O(log n) time, insertion/deletion of k-edge monotone chains in O(log n+k) time, and answers queries in O(log(2) n) time, with O(n) space, where n is the current size of subdivision S. The techniques described also allow for the dual operations expand and contract to be implemented in O(log n) time, leading to an improved method for spatial point location in a 3-dimensional convex subdivision. In addition, the interlaced-tree approach is applied to on-line point location (where one builds incrementally), improving the query bound to O(log n log log n) time and the update bounds to O(1) S amortized time in this case. This appears to be the first on-line method to achieve a polylogarithmic query time and constant update time.

关键词： computational geometry point location centroid decomposition dynamic data structures on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

On Bayes methods for on-line Boolean prediction

引用

ALGORITHMICA 1998年第1-2期22卷 112-137页

作者： Cesa-Bianchi, N Helmbold, DP Panizza, S Univ Milan DSI I-20135 Milano Italy Univ Calif Santa Cruz Dept Comp Sci Santa Cruz CA 95064 USA

We examine a general Bayesian framework for constructing on-line prediction algorithms in the experts setting. These algorithms predict the bits of an unknown Boolean sequence using the advice of a finite set of experts. In this framework we use probabilistic assumptions on the unknown sequence to motivate prediction strategies. However, the relative bounds that we prove on the number of prediction mistakes made by these strategies hold for any sequence. The Bayesian framework provides a unified derivation and analysis of previously known prediction strategies, such as the Weighted Majority and Binomial Weighting algorithms. Furthermore, it provides a principled way of automatically adapting the parameters of Weighted Majority to the sequence, in contrast to previous ad hoc doubling techniques. Finally, we discuss the generalization of our methods to algorithms making randomized predictions.

关键词： Boolean prediction on-line algorithms Bayes theory

来源：评论

学校读者我要写书评

暂无评论

Theoretical analysis for communication-induced checkpointing protocols with rollback-dependency trackability

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1998年第10期9卷 963-971页

作者： Tsai, JC Kuo, SY Wang, YM Natl Taiwan Univ Dept Elect Engn Taipei 106 Taiwan Microsoft Corp Microsoft Res Redmond WA 98052 USA

Rollback-Dependency Trackability (RDT) is a property that states that all rollback dependencies between local checkpoints are on-line trackable by using a transitive dependency vector. In this paper, we address three fundamental issues in the design of communication-induced checkpointing protocols that ensure RDT. First, we prove that the following intuition commonly assumed in the literature is in fact false: If a protocol forces a checkpoint only at a stronger condition, then it must take, at most, as many forced checkpoints as a protocol based on a weaker condition. This result implies that the common approach of sharpening the checkpoint-inducing condition by piggybacking more control information on each message may not always yield a more efficient protocol. Next, we prove that there is no optimal on-line RDT protocol that takes fewer forced checkpoints than any other RDT protocol for all possible communication patterns. Finally, since comparing checkpoint-inducing conditions is not sufficient for comparing protocol performance, we present some formal techniques for comparing the performance of several existing RDT protocols.

关键词： rollback-dependency trackability on-line algorithms checkpointing rollback recovery communication-induced protocols

来源：评论

学校读者我要写书评

暂无评论

A competitive analysis of the list update problem with lookahead

引用

THEORETICAL COMPUTER SCIENCE 1998年第1-2期197卷 95-109页

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

We consider the question of lookahead in the list update problem: What improvement can be achieved in terms of competitiveness if an on-line algorithm sees not only the present request to be served but also some future requests? We introduce two different models of lookahead and study the list update problem using these models. We develop lower bounds on the competitiveness that can be achieved by deterministic on-line algorithms with lookahead. Furthermore, we present on-line algorithms with lookahead that are competitive against static off-line algorithms. (C) 1998-Elsevier Science B.V. All rights reserved.

关键词： linear lists on-line algorithms competitive analysis lookahead

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：