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

Online conflict-free coloring of intervals

SCIENTIA IRANICA 2014年第6期21卷 2138-2141页

作者： Abam, M. A. Seraji, M. J. Rezaei Shadravan, M. Sharif Univ Technol Dept Comp Engn Tehran Iran

In this paper, we study the problem of online conflict-free coloring of intervals on a line, where each newly inserted interval must be assigned a color upon insertion such that the coloring remains conflict-free, i.e. for each point p in the union of the current intervals, there must be an interval I with a unique color among all intervals covering p. We first present a simple algorithm which uses O(root n) colors where n is the number of current intervals. Next, we propose an CF-coloring of intervals which uses O(log(3) n) colors. (C) 2014 Sharif University of Technology. All rights reserved.

关键词： Frequency assignment Conflict-free coloring Intervals on-line algorithms Computational geometry

来源：评论

学校读者我要写书评

暂无评论

A fast work function algorithm for solving the k-server problem

引用

CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH 2013年第1期21卷 187-205页

作者： Rudec, Tomislav Baumgartner, Alfonzo Manger, Robert Univ Zagreb Dept Math Zagreb 10000 Croatia Univ Osijek Fac Elect Engn Osijek 31000 Croatia

This paper deals with the work function algorithm (WFA) for solving the on-line k-server problem. The paper addresses some practical aspects of the WFA, such as its efficient implementation and its true quality of serving. First, an implementation of the WFA is proposed, which is based on network flows, and which reduces each step of the WFA to only one minimal-cost maximal flow problem instance. Next, it is explained how the proposed implementation can further be simplified if the involved metric space is finite. Also, it is described how actual computing of optimal flows can be speeded up by taking into account special properties of the involved networks. Some experiments based on the proposed implementation and improvements are presented, where actual serving costs of the WFA have been measured on very large problem instances and compared with costs of other algorithms. Finally, suitability of the WFA for solving real-life problems is discussed.

关键词： On-line problems on-line algorithms k-server problem Work function algorithm Implementation Network flows

来源：评论

学校读者我要写书评

暂无评论

P2P-FISM: Mining (recently) frequent item sets from distributed data streams over P2P network

引用

INFORMATION PROCESSING LETTERS 2013年第19-21期113卷 793-798页

作者： Farzanyar, Zahra Kangavari, Mohammadreza Cercone, Nick Iran Univ Sci & Technol Dept Comp Engn Tehran Iran York Univ Dept Comp Sci & Engn Toronto ON M3J 2R7 Canada

Data intensive large-scale distributed systems like peer-to-peer (P2P) networks are finding large number of applications for social networking, file sharing networks, etc. Global data mining in such P2P environments may be very costly due to the high scale and the asynchronous nature of the P2P networks. The cost further increases in the distributed data stream scenario where peers receive continuous sequence of transactions rapidly. In this paper, we develop an efficient local algorithm, P2P-FISM, for discovering of the network-wide recent frequent itemsets. The algorithm works in a completely asynchronous manner, imposes low communication overhead, a necessity for scalability, transparently tolerates network topology changes, and quickly adapts to changes in the data stream. The paper demonstrates experimental results to corroborate the theoretical claims. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Data stream on-line algorithms P2P distributed systems P2P data mining

来源：评论

学校读者我要写书评

暂无评论

Buffer overflow management with class segregation

引用

INFORMATION PROCESSING LETTERS 2013年第4期113卷 145-150页

作者： Al-Bawani, Kamal Souza, Alexander Rhein Westfal TH Aachen Dept Comp Sci Aachen Germany Humboldt Univ Dept Comp Sci Berlin Germany

We consider a new model for buffer management of network switches with Quality of Service (QoS) requirements. A stream of packets, each attributed with a value representing its Class of Service (CoS), arrives over time at a network switch and demands a further transmission. The switch is equipped with multiple queues of limited capacities, where each queue stores packets of one value only. The objective is to maximize the total value of the transmitted packets (i.e., the weighted throughput). We analyze a natural greedy algorithm, GREEDY, which sends in each time step a packet with the greatest value. For general packet values (v(1) < ... < v(m)), we show that GREEDY is (1 + r)-competitive, where r = max(1 <= i <= m-1){v(i)/v(i+1)}. Furthermore, we show a lower bound of 2 - v(m)/Sigma(m)(i=1) v(i) on the competitiveness of any deterministic online algorithm. In the special case of two packet values (1 and alpha > 1), GREEDY is shown to be optimal with a competitive ratio of (alpha + 2)/(alpha + 1). (C) 2013 Elsevier B.V. All rights reserved.

关键词： on-line algorithms Competitive analysis Buffer management

来源：评论

学校读者我要写书评

暂无评论

Online version of the theorem of Thue

引用

INFORMATION PROCESSING LETTERS 2013年第5-6期113卷 193-195页

作者： Grytczuk, Jaroslaw Szafruga, Piotr Zmarz, Michal Jagiellonian Univ Fac Math & Comp Sci Theoret Comp Sci Dept Krakow Poland Warsaw Univ Technol Fac Math & Informat Sci Warsaw Poland

A sequence S is nonrepetitive if no two adjacent blocks of S are the same. In 1906 Thue proved that there exist arbitrarily long nonrepetitive sequences over 3 symbols. We consider the online variant of this result in which a nonrepetitive sequence is constructed during a play between two players: Bob is choosing a position in a sequence and Alice is inserting a symbol on that position taken from a fixed set A. The goal of Bob is to force Alice to create a repetition, and if he succeeds, then the game stops. The goal of Alice is naturally to avoid that and thereby to construct a nonrepetitive sequence of any given length. We prove that Alice has a strategy to play arbitrarily long provided the size of the set A is at least 12. This is the online version of the theorem of Thue. The proof is based on nonrepetitive colorings of outerplanar graphs. On the other hand, one can prove that even over 4 symbols Alice has no chance to play for too long. The minimum size of the set of symbols needed for the online version of Thue's theorem remains unknown. (C) 2013 Elsevier B.V. All rights reserved.

关键词： on-line algorithms Nonrepetitive sequence Thue's theorem

来源：评论

学校读者我要写书评

暂无评论

A Heaviest Hitters Limiting Mechanism with O(1) Time Complexity for Sliding-Window Data Streams

引用

JOURNAL OF INTERNET TECHNOLOGY 2013年第1期14卷 117-126页

作者： Koutsiamanis, Remous-Aris Efraimidis, Pavlos S. Democritus Univ Thrace Dept Elect & Comp Engn Komotini Greece

In this work we address the problem of identifying and limiting the heaviest hitters in a sliding-window data stream. We propose the first, to our knowledge, exact (i.e., not approximate) algorithm which achieves O(1) with high probability time complexity in both update and query operations. Additionally, it tracks the first and last item;of any itemset in the window in O(1) time complexity as well as the lightest hitters with no additional computational costs. These properties allow us to efficiently implement a mechanism to limit the heaviest hitters by evicting them from or not allowing them in the window. We describe the algorithms and data structure which implement this functionality, we explain how they can be used to accomplish the goal of limiting the heaviest hitters and perform experiments to produce quantitative results to support our theoretical arguments.

关键词： Mining Heaviest hitters Data streams Sliding window on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

List update with probabilistic locality of reference

引用

INFORMATION PROCESSING LETTERS 2012年第13期112卷 540-543页

作者： Dorrigiv, Reza Lopez-Ortiz, Alejandro Univ Waterloo Cheriton Sch Comp Sci Waterloo ON N2L 3G1 Canada

In this paper we study the performance of list update algorithms under arbitrary distributions that exhibit strict locality of reference and prove that Move-To-Front (MTF) is the best list update algorithm under any such distribution. We also show that the performance of MTF depends on the amount of locality of reference, while the performance of any static list update algorithm is independent of the amount of locality. (C) 2012 Published by Elsevier B.V.

关键词： on-line algorithms Analysis of algorithms Data structures List update Locality of reference

来源：评论

学校读者我要写书评

暂无评论

Immediate detection of predicates in pervasive environments

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2012年第2期72卷 219-230页

作者： Kshemkalyani, Ajay D. Univ Illinois Chicago IL 60607 USA

An important problem in pervasive environments is detecting predicates on sensed variables in an asynchronous distributed setting to determine context and to respond. We do not assume the availability of synchronized physical clocks because they may not be available or may be too expensive for predicate detection in such environments with a (relatively) low event occurrence rate. We address the problem of detecting each occurrence of a global predicate, at the earliest possible instant, by proposing a suite of three on-line middleware protocols having varying degrees of accuracy. We analyze the degree of accuracy for the proposed protocols. The extent of false negatives and false positives is determined by the run-time message processing latencies. (C) 2011 Elsevier Inc. All rights reserved.

关键词： Sensor networks Predicate detection Pervasive computing on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

An improved analysis of SRPT scheduling algorithm on the basis of functional optimization

引用

INFORMATION PROCESSING LETTERS 2012年第23期112卷 911-915页

作者： Fujiwara, Hiroshi Sekiguchi, Yoshiyuki Toyohashi Univ Technol Dept Comp Sci & Engn Toyohashi Aichi 4418580 Japan Tokyo Univ Marine Sci & Technol Fac Marine Technol Koto Ku Tokyo 1358533 Japan

The competitive performance of the SRPT scheduling algorithm has been open for a long time except for being 2-competitive, where the objective is to minimize the total completion time. Chung et al. proved that the SRPT algorithm is 1.857-competitive. In this paper we improve their analysis and show a 1.792-competitiveness. We clearly mention that our result is not the best so far, since Sitters recently proved the algorithm is 1.250-competitive. Nevertheless, it is still well worth reporting our analytical method;our analysis is based on the modern functional optimization, which can scarcely be found in the literature on the analysis of algorithms. Our aim is to illustrate the potentiality of functional optimization with a concrete application. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Analysis of algorithms on-line algorithms Scheduling Competitive analysis Functional analysis

来源：评论

学校读者我要写书评

暂无评论

Optimal randomized algorithm for a generalized ski-rental with interest rate

引用

INFORMATION PROCESSING LETTERS 2012年第13期112卷 548-551页

作者： Yang, Xingyu Zhang, Weiguo Zhang, Yong Xu, Weijun S China Univ Technol Sch Business Adm Guangzhou 510640 Guangdong Peoples R China

We introduce the continuously compounded interest rate into a generalized ski-rental problem with two options: either pay some rental proportionally to the usage time (the rent option), or buy the equipment and then pay some reduced rental proportionally to the usage time (the generalized buy option). Under the framework of competitive analysis. a randomized algorithm for the modified model is constructed and then is proved optimal by Yao's Lemma, and thus the optimal competitive ratio is obtained. The result shows that the introduction of the interest rate puts off the optimal purchase date and diminishes the uncertainty involved in the decision making. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Ski-rental Competitive analysis on-line algorithms Randomized algorithms Interest rate

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：