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

JOURNAL OF SCHEDULING 2004年第5期7卷 349-364页

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

We analyze preemptive on-line scheduling against randomized adversaries, with the goal to finish an unknown distinguished target job. Our motivation comes froth clinical gene search projects, but the subject leads to general theoretical questions of independent interest, including some natural but unusual probabilistic models. We study problem versions with known and unknown processing tithes of jobs and target probabilities, and models where the on-line player gets some randomized extra information about the target. For some versions we get optimal competitive ratios, expressed in terms of given parameters of instances.

关键词： on-line algorithms randomized adversary searching Bayesian models

来源：评论

学校读者我要写书评

暂无评论

Lease or financial lease? Deterministic strategies for on-line financial lease problem with the second-hand transaction

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第2期44卷 1248-1264页

作者： Zhang, Yong Li, Jiahao Yang, Xingyu Wang, Xiaohui Guangdong Univ Technol Sch Management Guangzhou 510520 Guangdong Peoples R China Tianjin Univ Technol & Educ Sch Econ & Management Tianjin 300222 Peoples R China

The residual value of the equipment is an important and inevitable issue for any decision-making process of equipment leasing. In this paper, we present an on-line financial leasing problem considering the second-hand transaction issue, i.e. the equipment can be sold in the secondary market when it is no longer needed. Using competitive analysis, the optimal deterministic strategies are given to deal with the financial leasing problem. Finally, to test the performance of the proposed on-line financial leasing strategies, several numerical experiments are conducted.

关键词： Deterministic leasing strategy Financial lease Second-hand transaction Competitive analysis on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

The relative worst-order ratio applied to paging

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2007年第5期73卷 818-843页

作者： Boyar, Joan Favrholdt, Lene M. Larsen, Kim S. Odense Univ Dept Math & Comp Sci DK-5230 Odense Denmark

The relative worst-order ratio, a relatively new measure for the quality of on-line algorithms, is extended and applied to the paging problem. We obtain results significantly different from those obtained with the competitive ratio. First, we devise a new deterministic paging algorithm, Retrospective-LRU, and show that, according to the relative worst-order ratio and in contrast with the competitive ratio, it performs better than LRU. Our experimental results, though not conclusive, are slightly positive and leave it possible that Retrospective-LRU or similar algorithms may be worth considering in practice. Furthermore, the relative worst-order ratio (and practice) indicates that LRU is better than the marking algorithm FWF, though all deterministic marking algorithms have the same competitive ratio. Look-ahead is also shown to be a significant advantage with this new measure, whereas the competitive ratio does not reflect that look-ahead can be helpful. Finally, with the relative worst-order ratio, as with the competitive ratio, no deterministic marking algorithm can be significantly better than LRU, but the randomized algorithm MARK is better than LRU. (c) 2007 Elsevier Inc. All rights reserved.

关键词： on-line algorithms relative worst-order ratio paging LRU RLRU look-ahead

来源：评论

学校读者我要写书评

暂无评论

ON THE POWER OF RANDOMIZATION FOR JOB SHOP SCHEDULING WITH k-UNITS LENGTH TASKS

引用

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS 2009年第2期43卷 189-207页

作者： Moemke, Tobias ETH Dept Informat CH-8092 Zurich Switzerland

In the job shop scheduling problem k-units-J(m), there are m machines and each machine has an integer processing time of at most k time units. Each job consists of a permutation of m tasks corresponding to all machines and thus all jobs have an identical dilation D. The contribution of this paper are the following results;(i) for d = o(root D) jobs and every fixed k, the makespan of an optimal schedule is at most D + o(D), which extends the result of [3] for k = 1;(ii) a randomized on-line approximation algorithm for k-units-J(m) is presented. This is the on-line algorithm with the best known competitive ratio against an oblivious adversary for d = o(root D) and k > 1;(iii) different processing times yield harder instances than identical processing times. There is no 5/3 competitive deterministic on-line algorithm for k-units-J(m), whereas the competitive ratio of the randomized on-line algorithm of (ii) still tends to 1 for d = o(root D).

关键词： on-line algorithms randomization competitive ratio scheduling

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Online 2-stage stable matching

引用

DISCRETE APPLIED MATHEMATICS 2023年 341卷 394-405页

作者： Bampis, Evripidis Escoffier, Bruno Youssef, Paul Sorbonne Univ CNRS LIP6 4 Pl Jussieu F-75005 Paris France Inst Univ France Paris France Univ Grenoble Alpes LIG F-38400 St Martin Dheres France

We focus on an online 2-stage problem, motivated by the following situation: consider a system where students shall be assigned to universities. There is a first round where some students apply, and a first (stable) matching M1 has to be computed. However, some students may decide to leave the system (change their plan, go to a foreign university, or to some institution not in the system). Then, in a second round (after these deletions), we shall compute a second (final) stable matching M2. As it is undesirable to change assignments, the goal is to minimize the number of divorces/modifications between the two stable matchings M1 and M2. Then, how should we choose M1 and M2? We show that there is an optimal online algorithm to solve this problem. In particular, thanks to a dominance property, we show that we can optimally compute M1 without knowing the students that will leave the system. We generalize the result to some other possible modifications in the input (i.e., in the sets of students and/or open positions in universities). We also tackle the case of more stages, showing that no competitive (online) algorithm can be achieved for the considered problem as soon as there are 3 stages.(c) 2023 Elsevier B.V. All rights reserved.

关键词： Stable matching on-line algorithms 2-stage optimization

来源：评论

学校读者我要写书评

暂无评论

PRACTICAL CELLULAR DIVIDERS

引用

IEEE TRANSACTIONS ON COMPUTERS 1990年第5期39卷 605-614页

作者： PREPARATA, FP VUILLEMIN, JE INST NATL RECH INFORMAT & AUTOMAT F-78150 ROCQUENCOURTFRANCE ECOLE NORM SUPER F-75231 PARIS 05FRANCE

A discussion is presented of parallel division algorithms that can be classified among modified higher radix nonrestoring online division methods, where redundant representations are extensively utilized to speed up the operation. The network realizations of these algorithms are cellular, or even systolic with exclusively local control; they have both size (area) and time of O(n), where n is the length of the dividend representation. The same structures can also be used as a signed, digit-serial multiplier. When suitably equipped with some control and a few registers, the divider/multiplier brings remarkable performance to large modular arithmetic, RSA cryptography, and greatest common divisor computations. They are also of interest for the design of floating-point units and signal processing applications

关键词： Computer arithmetic on-line algorithms Division Multiplication greatest-common-divisor systolic networks

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Management of multi-queue switches in QoS networks

引用

ALGORITHMICA 2005年第1-2期43卷 81-96页

作者： Azar, Y Richter, Y Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel

The concept of Quality of Service (QoS) networks has gained growing attention recently, as the traffic volume in the Internet constantly increases, and QoS guarantees are essential to ensure proper operation of most communication-based applications. A QoS switch serves m incoming queues by transmitting packets arriving to these queues through one output port, one packet per time step. Each packet is marked with a value indicating its priority in the network. Since the queues have bounded capacities and the rate of arriving packets can be much higher than the transmission rate, packets can be lost due to insufficient queue space. The goal is to maximize the total value of transmitted packets. This problem encapsulates two dependent questions: buffer management, namely which packets to admit into the queues, and scheduling, i.e. which queue to use for transmission in each time step. We use competitive analysis to study online switch performance in QoS-based networks. Specifically, we provide a novel generic technique that decouples the buffer management and scheduling problems. Our technique transforms any single-queue buffer management policy (preemptive or non-preemptive) to a scheduling and buffer management algorithm for our general m queues model, whose competitive ratio is at most twice the competitive ratio of the given buffer management policy. We use our technique to derive concrete algorithms for the general preemptive and non-preemptive cases, as well as for the interesting special cases of the 2-value model and the unit-value model. We also provide a 1.58-competitive randomized algorithm for the unit-value case. This case is interesting by itself since most current networks (e.g. IP networks) do not yet incorporate full QoS capabilities, and treat all packets equally.

关键词： on-line algorithms competitive ratio competitiveness multi-queue switch packet switching buffer management quality of Service

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：