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

Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs

DISCRETE APPLIED MATHEMATICS 2007年第2期155卷 119-136页

作者： Caragiannis, Ioannis Fishkin, Aleksei V. Kaklamanis, Christos Papaioannou, Evi Univ Patras Res Acad Comp Techol Inst Rion 26500 Greece Univ Patras Dept Comp Engn & Informat Rion 26500 Greece Max Planck Inst Informat D-66123 Saarbrucken Germany

We study the on-line version of the maximum independent set problem, for the case of disk graphs which are graphs resulting from intersections of disks on the plane. In particular, we investigate whether randomization can be used to break known lower bounds for deterministic on-line independent set algorithms and present new upper and lower bounds. (c) 2006 Elsevier B.V. All rights reserved.

关键词： on-line algorithms competitive analysis maximum independent set disk graphs

来源：评论

学校读者我要写书评

暂无评论

Learning parities in the mistake-bound model

引用

INFORMATION PROCESSING LETTERS 2010年第1期111卷 16-21页

作者： Buhrman, Harry Garcia-Soriano, David Matsliah, Arie CWI Amsterdam Amsterdam Netherlands

We study the problem of learning parity functions that depend on at most k variables (k-parities) attribute-efficiently in the mistake-bound model. We design a simple, deterministic, polynomial-time algorithm for learning k-parities with mistake bound O(n(1-1/k)). This is the first polynomial-time algorithm to learn omega(1)-parities in the mistake-bound model with mistake bound o(n). Using the standard conversion techniques from the mistake-bound model to the PAC model, our algorithm can also be used for learning k-parities in the PAC model. In particular, this implies a slight improvement over the results of Klivans and Servedio (2004) [1] for learning k-parities in the PAC model. We also show that the (O) over tilde (n(k/2)) time algorithm from Klivans and Servedio (2004) [1] that PAC-learns k-parities with sample complexity O(k log n) can be extended to the mistake-bound model. (c) 2010 Elsevier B.V. All rights reserved.

关键词： on-line algorithms Parities Mistake-bound Attribute-efficient learning

来源：评论

学校读者我要写书评

暂无评论

On the additive constant of the k-server Work Function Algorithm

引用

INFORMATION PROCESSING LETTERS 2010年第24期110卷 1120-1123页

作者： Emek, Yuval Fraigniaud, Pierre Korman, Amos Rosen, Adi CNRS F-75700 Paris France Univ Paris 11 Paris France Univ Paris Diderot Paris France Tel Aviv Univ Sch Elect Engn IL-69978 Tel Aviv Israel Microsoft Israel R&D Ctr Herzliyya Israel

We consider the Work Function Algorithm for the k-server problem (Chrobak and Larmore, 1991: Koutsoupias and Papadimitriou, 1995) [2,4]. We show that if the Work Function Algorithm is c-competitive, then it is also strictly (2c)-competitive. As a consequence of (Koutsoupias and Papadimitriou, 1995) [4] this also shows that the Work Function Algorithm is strictly (4k - 2)-competitive. (C) 2010 Elsevier B.V. All rights reserved.

关键词： on-line algorithms k-server problem

来源：评论

学校读者我要写书评

暂无评论

Short proofs for online multiclass prediction on graphs

引用

INFORMATION PROCESSING LETTERS 2010年第8-9期110卷 309-311页

作者： Fakcharoenphol, Jittat Kijsirikul, Boonserm Kasetsart Univ Dept Comp Engn Bangkok 10900 Thailand Chulalongkorn Univ Dept Comp Engn Bangkok 10330 Thailand

We present short proofs on the mistake bounds of the 1-nearest neighbor algorithm on an online prediction problem of path labels. The algorithm is one of key ingredients in the algorithm by Herbster. Lever, and Pontil for general graphs. Our proofs are combinatorial and naturally show that the algorithm works when the set of labels is not binary. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Analysis of algorithms on-line algorithms On-line learning Prediction on graphs

来源：评论

学校读者我要写书评

暂无评论

Scheduling Jobs on Grid Processors

引用

ALGORITHMICA 2010年第4期57卷 819-847页

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

We study a new kind of on-line bin packing, motivated by a problem arising when scheduling jobs on the Grid. In this bin packing problem, the set of items is given at the beginning, and variable-sized bins arrive one by one. We analyze the problem using both the competitive ratio and the relative worst order ratio, observing that the two measures often lead to different conclusions. A closely related problem was introduced by Zhang (Discrete Appl. Math. 72:193-197, 1997). Our main result answers a question posed in that paper in the affirmative: we give an algorithm with a competitive ratio strictly better than 2, for our problem as well as Zhang's problem. For identical bins, the new algorithm has essentially the same performance as FFD (First-Fit-Decreasing).

关键词： Grid scheduling problem Zhang's bin packing problem on-line algorithms First-Fit-Decreasing

来源：评论

学校读者我要写书评

暂无评论

Weighted nearest neighbor algorithms for the graph exploration problem on cycles

引用

INFORMATION PROCESSING LETTERS 2010年第3期110卷 93-98页

作者： Asahiro, Yuichi Miyano, Eiji Miyazaki, Shuichi Yoshimuta, Takuro Kyushu Inst Technol Dept Syst Design & Informat Fukuoka 8208502 Japan Kyushu Sangyo Univ Dept Informat Sci Fukuoka 8138503 Japan Kyoto Univ Acad Ctr Comp & Media Studies Kyoto 6068501 Japan

In the graph exploration problem, a searcher explores the whole set of nodes of an unknown graph. We assume that all the unknown graphs are undirected and connected. The searcher is not aware of the existence of ail edge until he/she visits one of its endpoints. The searcher's task is to visit all the nodes and go back to the starting node by traveling a tour as short as possible. One of the simplest strategies is the nearest neighbor algorithm (NN). which always chooses the unvisited node nearest to the searcher's current position. The weighted NN (WNN) is an extension of NN, which chooses the next node to visit by using the weighted distance. It is known that WNN with weight 3 is 16-competitive for planar graphs. In this paper we prove that NN achieves the competitive ratio of 1.5 for cycles. In addition, we show that the analysis for the competitive ratio of NN is tight by providing an instance for which the bound of 1.5 is attained, and NN is the best for cycles among WNN with all possible weights. Furthermore, we prove that no online algorithm to explore cycles is better than 1.25-competitive. (C) 2009 Elsevier B.V. All rights reserved.

关键词： on-line algorithms Graph exploration problem Weighted nearest neighbor Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Finding frequent items over sliding windows with constant update time

引用

INFORMATION PROCESSING LETTERS 2010年第7期110卷 257-260页

作者： Hung, Regant Y. S. Lee, Lap-Kei Ting, H. F. Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

In this paper, we consider the problem of finding epsilon-approximate frequent items over a sliding window of size N. A recent work by Lee and Ting (2006) [7] solves the problem by giving an algorithm that supports O(1/epsilon) query and update time, and uses O(1/epsilon) space. Their query time and memory usage are essentially optimal, but the update time is not. We give a new algorithm that supports O(1) update time with high probability while maintaining the query time and memory usage as O(1/epsilon). (C) 2010 Elsevier B.V. All rights reserved.

关键词： Approximation algorithms on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

Randomized algorithms for online bounded bidding

引用

INFORMATION PROCESSING LETTERS 2010年第12-13期110卷 503-506页

作者： Epstein, Leah Levin, Asaf Univ Haifa Dept Math IL-31905 Haifa Israel Technion Israel Inst Technol Fac Ind Engn & Management IL-32000 Haifa Israel

In the online bidding problem, a bidder is trying to guess a positive number T. by placing bids until the value of the bid is at least T. The bidder is charged with the sum of the bids. In the bounded online bidding problem, a parameter k is given, and the bidder is charged only with the largest k bids. It is known that the online bidding problem admits a 4-competitive deterministic algorithm, and an e-competitive randomized algorithm, and these results are best possible. The deterministic best possible competitive ratio for the online bounded bidding problem is also known, for any value of k. We study the randomized bounded online bidding problem, and show that for any k > 2, randomization is helpful, that is, it allows to design an algorithm of a smaller competitive ratio compared to the best deterministic algorithm. In contrast, for k = 2, we show a lower bound of 2 on the competitive ratio of any randomized algorithms, matching the upper bound achieved by a trivial deterministic algorithm, which tests all possible bids sequentially. (C) 2010 Elsevier B.V. All rights reserved.

关键词： on-line algorithms Online bidding Competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Optimal on-line colorings for minimizing the number of ADMs in optical networks

引用

JOURNAL OF DISCRETE algorithms 2010年第2期8卷 174-188页

作者： Shalom, Mordechai Wong, Prudence W. H. Zaks, Shmuel Technion Dept Comp Sci Haifa Israel Univ Liverpool Dept Comp Sci Liverpool Merseyside England TelHai Acad Coll Tel Hai Israel

We consider the problem of minimizing the number of ADMs in optical networks. All previous theoretical studies of this problem dealt with the off-line case, where all the lightpaths are given in advance. In a real-life situation, the requests (lightpaths) arrive at the network on-line, and we have to assign them wavelengths so as to minimize the switching cost. This study is thus of great importance in the theory of optical networks. We present a deterministic on-line algorithm for the problem, and show its competitive ratio to be 74. We show that this result is best possible in general. Moreover, we show that even for the ring topology network there is no on-line algorithm with competitive ratio better than 74. We show that on path topology the competitive ratio of the algorithm is 32. This is optimal for in this topology. The lower bound on ring topology does not hold when the ring is of bounded size. We analyze the triangle topology and show a tight bound of 53 for it. The analyses of the upper bounds, as well as those for the lower bounds, are all using a variety of proof techniques, which are of interest by their own, and which might prove helpful in future research on the topic.(C) 2009 Elsevier B. V. All rights reserved.

关键词： Wavelength assignment Wavelength division multiplexing (WDM) Optical networks Add-drop multiplexer (ADM) on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

Preemptive and non-preemptive on-line algorithms for scheduling with rejection on two uniform machines

引用

COMPUTING 2006年第1-2期76卷 149-164页

作者： Dósa, G He, Y Univ Veszprem Dept Math H-8201 Veszprem Hungary Zhejiang Univ Dept Math Hangzhou 310027 Peoples R China Zhejiang Univ State Key Lab CAD & CG Hangzhou 310027 Peoples R China

In this paper, we consider the problem of on-line scheduling a job sequence on two uniform machines. A job can be either rejected, in which case we pay its penalty, or scheduled on machines, in which case it contributes its processing time to the makspan of the constructed schedule. The objective is to minimize the sum of the makespan of the schedule for all accepted jobs and the penalties of all rejected jobs. Both preemptive and non-preemptive versions are considered. For the preemptive version, we present an optimal on-line algorithm with a competitive ratio 1/2 + root 1/4 + 1/s for any s >= 1, where s is the machine speed ratio. For the non-preemptive version, we present an improved lower bound. Moreover, as an optimal algorithm for s >= 1.6180 is known, we present a modified version of the known algorithm, and show that it becomes optimal for any 1.3852 <= s < 1.6180 and has a smaller competitive ratio than that of original version for any 1 <= s < 1.3852. The maximum gap between its competitive ratio and the lower bound is 0.0534.

关键词： scheduling rejection on-line algorithms preemption competitive analysis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：