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

The on-line first-fit algorithm for radio frequency assignment problems

INFORMATION PROCESSING LETTERS 2002年第4期84卷 195-199页

作者： Tsai, YT Lin, YL Hsu, FR Department of Computer Science and Information Management Providence University Taiwan Republic of China Department of Accounting Providence University Taiwan Republic of China

The radio frequency assignment problem is to minimize the number of frequencies used by transmitters with no interference in radio communication networks;it can be modeled as the minimum vertex coloring problem on unit disk graphs. In this paper, we consider the on-line first-fit algorithm for the problem and show that the competitive ratio of the algorithm for the unit disk graph G with chi (G) = 2 is 3, where chi (G) is the chromatic number of G. Moreover, the competitive ratio of the algorithm for the unit disk graph G with chi (G) > 2 is at least 4 - 3/chi(G). The average performance for the algorithm is also discussed in this paper. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： unit disk graphs radio frequency assignment problems graph coloring problems on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

On delayed prediction of individual sequences

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2002年第7期48卷 1959-1976页

作者： Weinberger, MJ Ordentlich, E Hewlett Packard Labs Palo Alto CA 94304 USA

Prediction of individual sequences is investigated for cases in which the decision maker observes a delayed version of the sequence, or is forced to issue his/her predictions a number of steps in advance, with incomplete information. For finite action and observation spaces, it is shown that the prediction strategy that minimizes the worst case regret with respect to the Bayes envelope is obtained through subsampling of the sequence of observations. The result extends to the case of logarithmic loss. For finite-state (FS) reference prediction strategies, the delayed FS predictability (DFSP) is defined and related to its nondelayed counterpart. As in the nondelayed case, an efficient on-line decision algorithm, based on the incremental parsing rule, is shown to perform in the long run essentially as well as the best FS strategy determined in hindsight, with full knowledge of the given sequence of observations. An application to adaptive prefetching in computer memory architectures is discussed.

关键词： delayed prediction general loss functions Lempel-Ziv algorithm on-line algorithms sequential decision

来源：评论

学校读者我要写书评

暂无评论

New directions in traffic measurement and accounting

New directions in traffic measurement and accounting

引用

ACM SIGCOMM 2002 Conference

作者： Estan, C Varghese, G Univ Calif San Diego Dept Comp Sci & Engn La Jolla CA 92093 USA

ISBN: (纸本)158113570X

Accurate network traffic measurement is required for accounting, bandwidth provisioning and detecting DoS attacks. These applications see the traffic as a collection of flows they need to measure. As link speeds and the number of flows increase, keeping a counter for each flow is too expensive (using SRAM) or slow (using DRAM). The current state-of-the-art methods (Cisco's sampled NetFlow) which log periodically sampled packets are slow, inaccurate and resource-intensive. Previous work showed that at different granularities a small number of "heavy hitters" accounts for a large share of traffic. Our paper introduces a paradigm shift for measurement by concentrating only on large flows - those above some threshold such as 0.1% of the link capacity. We propose two novel and scalable algorithms for identifying the large flows: sample and hold and multistage filters, which take a constant number of memory references per packet and use a small amount of memory. If M is the available memory, we show analytically that the errors of our new algorithms are proportional to 1/M, by contrast, the error of an algorithm based on classical sampling is proportional to 1/rootM, thus providing much less accuracy for the same amount of memory. We also describe further optimizations such as early removal and conservative update that further improve the accuracy of our algorithms, as measured on real traffic traces, by an order of magnitude. Our schemes allow a new form of accounting called threshold accounting in which only flows above a threshold are charged by usage while the rest are charged a fixed fee. Threshold accounting generalizes usage-based and duration based pricing.

关键词： network traffic measurement usage based accounting scalability on-line algorithms identifying large flows

来源：评论

学校读者我要写书评

暂无评论

algorithms for the on-line travelling salesman

引用

ALGORITHMICA 2001年第4期29卷 560-581页

作者： Ausiello, G Feuerstein, E Leonardi, S Stougie, L Talamo, M Univ Rome La Sapienza Dipartimento Informat & Sistemist I-00198 Rome Italy Univ Buenos Aires Fac Ciencias Exactas & Nat Dept Computac RA-1428 Buenos Aires DF Argentina Univ Gen Sarmiento Inst Ciencias RA-1663 Buenos Aires DF Argentina Eindhoven Univ Technol Dept Math NL-5600 MB Eindhoven Netherlands

In this paper the problem of efficiently serving a sequence of requests presented in an on-line fashion located at points of a metric space is considered. We call this problem the On-line Travelling Salesman Problem (OLTSP). It has a variety of relevant applications in logistics and robotics. We consider two versions of the problem. In the first one the server is not required to return to the departure point after all presented requests have been served. For this problem we derive a lower bound on the competitive ratio of 2 on the real line. Besides, a 2.5-competitive algorithm for a wide class of metric spaces, and a 7/3-competitive algorithm for the real line are provided. For the other version of the problem, in which returning to the departure point is required, we present an optimal 2-competitive algorithm for the above-mentioned general class of metric spaces. If in this case the metric space is the real line we present a 1.75-competitive algorithm that compares with a approximate to1.64 lower bound.

关键词： on-line algorithms competitive analysis travelling salesman problem vehicle routing

来源：评论

学校读者我要写书评

暂无评论

Competitive on-line algorithms for distributed data management

引用

SIAM JOURNAL ON COMPUTING 1999年第3期28卷 1086-1111页

作者： Lund, C Reingold, N Westbrook, J Yan, D AT&T Bell Labs Res Florham Park NJ 07932 USA Yale Univ New Haven CT 06520 USA AT&T Bell Labs Dept Operat Res Holmdel NJ 07733 USA

Competitive on-line algorithms for data management in a network of processors are studied in this paper. A data object such as a file or a page of virtual memory is to be read and updated by various processors in the network. The goal is to minimize the communication costs incurred in serving a sequence of such requests. Distributed data management on important classes of networksd. Optimal algorithms with constant competitive ratios and matching lower bounds are obtained. Our algorithms use different interesting techniques, such as work functions [Chrobak and Larmore, Proc. DIMACS Workshop on on-line algorithms, AMS, 1991, pp. 11-64] and "factoring."

关键词： on-line algorithms competitive analysis memory management data management

来源：评论

学校读者我要写书评

暂无评论

Bounded space on-line bin packing: Best is better than first

引用

ALGORITHMICA 2001年第2期31卷 115-138页

作者： Csirik, J Johnson, DS Univ Szeged Dept Comp Sci Szeged Hungary AT&T Labs Res Florham Park NJ 07932 USA

We present a sequence of new linear-time, bounded-space, on-line bin packing algorithms, the K-Bounded Best Fit algorithms (BBFK). They are based on the Theta (n log n) Best Fit algorithm in much the same way as the Next-K Fit algorithms are based on the Theta (n log n) First Fit algorithm. Unlike the Next-K Fit algorithms, whose asymptotic worst-case ratios approach the limiting value of 17 from above as K --> infinity but never reach it, these new algorithms have worst-case ratio 17/10 for all K greater than or equal to 2. They also have substantially better average performance than their bounded-space competition, as we have determined based on extensive experimental results summarized here for instances with item sizes drawn independently and uniformly from intervals of the form (0, u], 0 < u 1. Indeed, for each u < 1, it appears that there exists a fixed memory bound K(u) such that BBFK(u) obtains significantly better packings on average than does the First Fit algorithm, even though the latter requires unbounded storage and has a significantly greater running time. For u = 1, BBFK can still outperform First Fit (and essentially equal Best Fit) if K is allowed to grow slowly. We provide both theoretical and experimental results concerning the growth rates required.

关键词： bin packing on-line algorithms first fit best fit

来源：评论

学校读者我要写书评

暂无评论

On-line load balancing in a hierarchical server topology

引用

SIAM JOURNAL ON COMPUTING 2001年第2期31卷 527-549页

作者： Bar-Noy, A Freund, A Naor, JS AT&T Labs Res Shannon Lab Florham Pk NJ 07932 USA Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

In a hierarchical server environment jobs are to be assigned in an on-line fashion to a collection of servers which form a hierarchy of capability: each job requests a specific server meeting its needs, but the system is free to assign it either to that server or to any other server higher in the hierarchy. Each job carries a certain load, which it imparts to the server it is assigned to. The goal is to nd a competitive assignment in which the maximum total load on a server is minimized. We consider the linear hierarchy in which the servers are totally ordered in terms of their capabilities. We investigate several variants of the problem. In the unweighted ( as opposed to weighted) problem all jobs have unit weight. In the fractional ( as opposed to integral) model a job may be assigned to several servers, each receiving some fraction of its weight. Finally, temporary ( as opposed to permanent) jobs may depart after being active for some finite duration of time. We show an optimal e-competitive algorithm for the unweighted integral permanent model. The same algorithm is (e+1)-competitive in the weighted case. Its fractional version is e-competitive even if temporary jobs are allowed. or the integral model with temporary jobs we show an algorithm which is 4-competitive in the unweighted case and 5-competitive in the weighted case. We show a lower bound of e for the unweighted case ( both integral and fractional). This bound is valid even with respect to randomized algorithms. We also show a lower bound of 3 for the unweighted integral model when temporary jobs are allowed. We generalize the problem and consider hierarchies in which the servers form a tree. In the tree hierarchy, any job assignable to a node is also assignable to the node's ancestors. We show a deterministic algorithm which is 4-competitive in the unweighted case and 5-competitive in the weighted case, where only permanent jobs are allowed. Randomizing this algorithm improves its competitiveness to e

关键词： on-line algorithms load balancing hierarchical servers temporary jobs resource procurement

来源：评论

学校读者我要写书评

暂无评论

Randomized on-line scheduling on two uniform machines

引用

JOURNAL OF SCHEDULING 2001年第2期4卷 71-92页

作者： Epstein, L Noga, J Seiden, S Sgall, J Woeginger, G Louisiana State Univ Dept Comp Sci Baton Rouge LA 70803 USA Tel Aviv Univ Interdisciplinary Ctr Sch Comp & Media Sci Herzliyya Israel Graz Tech Univ Inst Math A-8010 Graz Austria AS CR Math Inst CZ-11567 Prague Czech Republic Charles Univ Fac Math & Phys Dept Math Appl Prague Czech Republic

We study the problem of on-line scheduling on two uniform machines with speeds 1 and s greater than or equal to 1. A phi approximate to 1.61803 competitive deterministic algorithm was already known. We present the first randomized results for this problem: We show that randomization does not help for speeds s greater than or equal to 2, but does help for all s < 2. We present a simple memoryless randomized algorithm with competitive ratio (4 - s)(1 + s)/4 1.56250. We analyse other randomized algorithms that demonstrate that the randomized competitive ratio is at most 1.52778 for any s. These algorithms are barely random, i.e. they use only a constant number of random bits. Finally, we present a 1 + s/(s(2) + s + 1) competitive deterministic algorithm for the preemptive version of this problem. For any s, it is best possible even among randomized preemptive algorithms. Copyright (C) 2001 John Wiley & Sons, Ltd.

关键词： analysis of algorithms on-line algorithms competitive ratio scheduling

来源：评论

学校读者我要写书评

暂无评论

Stack-up algorithms for palletizing at delivery industry

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2001年第1期128卷 74-97页

作者： Rethmann, J Wanke, E Univ Dusseldorf Dept Comp Sci D-40225 Dusseldorf Germany

We study the following multi-objective combinatorial stack-up problem from delivery industry. Given a sequence q of labeled bins and two positive integers s and p. The aim is to stack-up the bins by iteratively removing one of the first s bins of the sequence and put it to one of p stack-up places. Each of these places has to contain bins of only one label, bins of different labels have to be placed on different places. If all bins of a label are removed from q, the corresponding place becomes available for bins of another label. We analyze the worst-case performance of simple algorithms for the stack-up problem that are very interesting from a practical point of view. In particular, we show that the so-called Most-Frequently on-line algorithm is (2,2)-competitive and has optimal worst-case on-line performance. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： on-line algorithms competitive analysis complexity approximation control

来源：评论

学校读者我要写书评

暂无评论

Point-to-point and multi-goal path planning for industrial robots

引用

JOURNAL OF ROBOTIC SYSTEMS 2001年第8期18卷 445-461页

作者： Wurll, C Henrich, D AMATEC Robot GMBH D-82110 Germering Germany Univ Kaiserslautern Fac Informat RESY D-67653 Kaiserslautern Germany

This article presents contributions in the field of path planning for industrial robots with 6 degrees of freedom. This work presents the results of our research in the last 4 years at the Institute for Process Control and Robotics at the University of Karlsruhe. The path planning approach we present works in an implicit and discretized C-space. Collisions are detected in the Cartesianworkspace by a hierarchical distance computation. The method is based on the A* search algorithm and needs no essential off-line computation. A new optimal discretization method leads to smaller search spaces, thus speeding up the planning. For a further acceleration, the search was parallelized. With a static load distribution good speedups can be achieved. By extending the algorithm to a bidirectional search, the planner is able to automatically select the easier search direction. The new dynamic switching of start and goal leads finally to the multi-goal path planning, which is able to compute a collision-free path between a set of goal poses (e.g., spot welding points) while minimizing the total path length. (C) 2001 John Wiley & Sons, Inc.

关键词： Bidirectional search Discretization Distributed and parallel processing Graph search Industrial robots on-line algorithms Path planning Search algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：