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

INFORMATION PROCESSING LETTERS 2008年第6期108卷 352-355页

作者： Gagie, Travis Dipartimento di Informatica Universita del Piemonte Orientate Italy

We show how any dynamic instantaneous compression algorithm can be converted to an asymmetric communication protocol, with which a server with high bandwidth can help clients with low bandwidth send it messages. Unlike previous authors, we do not assume the server knows the messages' distribution, and our protocols are the first to use only one round of communication for each message. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Data compression Asymmetric communication on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

The on-line asymmetric traveling salesman problem

引用

JOURNAL OF DISCRETE algorithms 2008年第2期6卷 290-298页

作者： Ausiello, Giorgio Bonifaci, Vincenzo Laura, Luigi Univ Roma La Sapienza Dept Comp & Syst Sci Via Salaria 113 I-00198 Rome Italy Eindhoven Univ Technol Dept Math & Comp Sci NL-5600 MB Eindhoven Netherlands

We consider two on-line versions of the asymmetric traveling salesman problem with triangle inequality. For the homing version, in which the salesman is required to return in the city where it started from, we give a 3+root 5/2-competitive algorithm and prove that this is best possible. For the nomadic version, the on-line analogue of the shortest asymmetric Hamiltonian path problem, we show that the competitive ratio of any on-line algorithm depends on the amount of asymmetry of the space in which the salesman moves. We also give bounds on the competitive ratio of on-line algorithms that are zealous, that is, in which the salesman cannot stay idle when some city can be served. (C) 2007 Elsevier B.V. All rights reserved.

关键词： on-line algorithms Competitive analysis Real time vehicle routing Asymmetric traveling salesman problem

来源：评论

学校读者我要写书评

暂无评论

Optimal orientation on-line 1

引用

34th Conference on Current Trends in Theory and Practice of Computer Science

作者： Duraj, Lech Gutowski, Grzegorz Jagiellonian Univ Theoret Comp Sci Dept PL-30387 Krakow Poland

ISBN: (数字)9783540775669

ISBN: (纸本)9783540775652

We consider the problem of graph orientation on-line. Orientation of a graph is an assignment of direction to every edge, resulting with a directed graph. The optimal orientation of a graph G is the one which maximizes the number of ordered pairs (u, v) of vertices of G for which there is a directed path from u to v in the resulting directed graph. Graph orientation on-line is a game in which one of the players constructs a graph by adding vertices one by one, so that the graph is connected at all times, and the second one assigns direction to the newly added edges. The goal of the second player is to maximize the number of connected pairs in the orientation, while the first player is trying to minimize it. We present asymptotically optimal strategies for both players and state that the game with n turns has a Theta (n log n/log log n) outcome.

关键词： on-line algorithms connectivity oriented graphs

来源：评论

学校读者我要写书评

暂无评论

On-line partitioning for on-line scheduling with resource conflicts

引用

7th International Conference on Parallel Processing and Applied Mathematics

作者： Borowiecki, Piotr Univ Zielona Dept Discrete Math & Theoret Comp Sci Gora Poland

ISBN: (纸本)9783540681052

Within this paper, we consider the problem of on-line partitioning the sequence of jobs which are competing for non-sharable resources. As a result of partitioning we get the subsets of jobs that form separate instances of the on-line scheduling problem. The objective is to generate a partition into the minimum number of instances such that the response time of any job in each instance is bounded by a given constant. Our research is motivated by applications in scheduling multiprocessor jobs on dedicated processors and channel assignment in WDM networks.

关键词： on-line scheduling resource conflicts maximum response time quality of service graph partitioning on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

On the competitiveness of a modified work function algorithm for solving the on-line k-server problem

On the competitiveness of a modified work function algorithm...

引用

30th International Conference on Information Technology Interfaces

作者： Rudec, Tomislav Manger, Robert Univ Osijek Fac Elect Engn Kneza Trpimira 2b Osijek 31000 Croatia Univ Zagreb Dept Math Zagreb 10000 Croatia

ISBN: (纸本)9789537138127

We study a modification of the well known work function algorithm (WFA) for solving the on-line k-server problem. Our modified WFA is based on a moving window, i.e. on the approximate work function that takes into account only a fixed number of most recent on-line requests. In this paper, we prove that, in contrast to the original WFA;the modified WFA is not competitive. Our proof is based on a suitably constructed problem instance showing that the performance of the modified WFA can be an arbitrary number of times worse than optimal.

关键词： on-line problems on-line algorithms k-server problem work function algorithm (WFA) moving windows competitiveness

来源：评论

学校读者我要写书评

暂无评论

Greedy online frequency allocation in cellular networks

引用

INFORMATION PROCESSING LETTERS 2007年第2-3期102卷 55-61页

作者： Chan, Joseph Wun-Tat Chin, Francis Y. L. Ye, Deshi Zhang, Yong Zhu, Hong Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China Kings Coll London Dept Comp Sci London WC2R 2LS England

The online frequency allocation problem for cellular networks has been well studied in these years. Given a mobile telephone network, whose geographical coverage area is divided into cells, phone calls are served by assigning frequencies to them, and no two calls emanating from the same or neighboring cells are assigned the same frequency. Assuming an online setting that the calls arrive one by one, the problem is to minimize the span of the frequencies used. In this paper, we study the greedy approach for the online frequency allocation problem, which assigns the minimal available frequency to a new call so that the call does not interfere with calls of the same cell or neighboring cells. If the calls have infinite duration, the competitive ratio of greedy algorithm has a tight upper bound of 17/7, which closes the gap of [17/7, 2.5) in [I. Caragiannis, C. Kaklamanis, E. Papaioannou, Efficient on-line frequency allocation and call control in cellular networks, Theory Comput. Syst. 35 (5) (2002) 521-543. A preliminary version of the paper appeared in SPAA 2000]. If the calls have finite duration, i.e., each call may be terminated at some time, the competitive ratio of the greedy algorithm has a tight upper bound of 3. (c) 2006 Elsevier B.V. All rights reserved.

关键词： on-line algorithms frequency allocation competitive analysis greedy algorithm cellular network

来源：评论

学校读者我要写书评

暂无评论

On-line optimal wavelength assignment in WDM networks with shared wavelength converter pool

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2007年第1期15卷 234-245页

作者： Zhang, Zhenghao Yang, Yuanyuan Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA SUNY Stony Brook Dept Elect & Comp Engn Stony Brook NY 11794 USA

In this paper, we study on-line wavelength assignment in wavelength-routed WDM networks under both unicast and multicast traffic where nodes in the networks have wavelength conversion ability. Since wavelength converters are still expensive and difficult to implement, we consider the case where nodes in networks have only a limited number of converters that are shared by all input channels. We study the problem of setting up connections in such networks using minimum number of wavelength converters. For unicast traffic, we first study the problem of setting up a lightpath on a given link-path with minimum number of conversions. We give a simple algorithm that solves it in O(tk) time where t is the number of links on the path and k is the number of wavelengths per fiber, as compared to the best known existing method that needs to construct an auxiliary graph and apply the Dijkstra's algorithm. We also consider the problem of setting up a lightpath while using wavelength converters at nodes with fewer available converters only when necessary, and give an O(tk) time algorithm. We then generalize this technique to WDM networks with arbitrary topologies and give an algorithm that sets up an optimal lightpath network-wide in O(Nk + Lk) time, where N and L are the number of nodes and links in the network, respectively. We also consider multicast traffic in this paper. Finding an optimal multicast light-tree is known to be NP-hard and is usually solved by first finding a link-tree then finding a light-tree on the link-tree. Finding an optimal link-tree is also NP-hard and has been extensively studied. Thus, we focus on the second problem which is to set up a light-tree on a given link-tree with minimum number of conversions. We propose a new multicast conversion model with which the output of the wavelength converter is split-table to save the usage of converters. We show that under this model the problem of setting up an optimal light-tree is NP-hard and then give efficien

关键词： multicast on-line algorithms optical networks routing shared wavelength converter pool unicast wavelength assignment wavelength conversion wavelength division multiplexing (WDM)

来源：评论

学校读者我要写书评

暂无评论

A short proof of optimality for the MIN cache replacement algorithm

引用

INFORMATION PROCESSING LETTERS 2007年第2-3期102卷 72-73页

作者： Van Roy, Benjamin Stanford Univ Stanford CA 94305 USA

The MIN algorithm is an offline strategy for deciding which item to replace when writing a new item to a cache. Its optimality was first established by Mattson et al. [R.L. Mattson, ***, D.R. Slutz, I.L. Traiger, Evaluation techniques for storage hierarchies, IBM Systems Journal 9 (2) (1970) 78-117] through a lengthy analysis. We provide a short and elementary proof based on a dynamic programming argument. (c) 2006 Elsevier B.V. All rights reserved.

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

来源：评论

学校读者我要写书评

暂无评论

Approximating total flow time on parallel machines

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2007年第6期73卷 875-891页

作者： Leonardi, Stefano Raz, Danny Univ Roma La Sapienza Dipartimento Informat & Sistemist I-00198 Rome Italy Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

We consider the problem of optimizing the total flow time of a stream of jobs that are released over time in a multiprocessor setting. This problem is NP-hard even when there are only two machines and preemption is allowed. Although the total (or average) flow time is widely accepted as a good measurement of the overall quality of service, no approximation algorithms were known for this basic scheduling problem. This paper contains two main results. We first prove that when preemption is allowed, Shortest Remaining Processing Time (SRPT) is an O(log(min{n/m, P})) approximation algorithm for the total flow time, where it is the number of jobs, In is the number of machines, and P is the ratio between the maximum and the minimum processing time of a job. We also provide an R(log( + P)) lower bound on the (worst case) competitive ratio of any randomized algorithm for the on-line problem in which jobs are known at their release times. Thus, we show that up to a constant factor SRPT is an optimal on-line algorithm. Our second main result addresses the non-preemptive case. We present a general technique that allows to transform any preemptive solution into a non-preemptive solution at the expense of an O(root n/m) factor in the approximation ratio of the total flow time. Combining this technique with our previous result yields an O(root n/m log n/m) approximation algorithm for this case. We also show an Omega (n(1/3-is an element of)) lower bound on the approximabiiity of this problem (assuming P not equal NP). (c) 2006 Elsevier Inc. All rights reserved.

关键词： parallel machine scheduling flow-time optimization on-line algorithms competitive analysis approximation 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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：