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

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

来源：评论

学校读者我要写书评

暂无评论

On the power of lookahead in on-line server routing problems

引用

THEORETICAL COMPUTER SCIENCE 2008年第2-3期408卷 116-128页

作者： Allulli, Luca Ausiello, Giorgio Bonifaci, Vincenzo Laura, Luigi Univ Roma La Sapienza Dipartimento Informat & Sistemist I-00185 Rome Italy Univ Aquila Dipartimento Ingn Elettr I-67040 Laquila Italy

We study the usefulness of lookahead in on-line server routing problems: if an on-line algorithm is not only informed about the requests released so far, but also has a limited ability to foresee future requests, what is the improvement that can be achieved in terms of the competitive ratio? We consider several on-line server routing problems in this setting, such as the on-line traveling salesman and the on-line traveling repairman problem. We show that the influence of lookahead can change considerably depending on the particular objective function and metric space considered. (C) 2008 Elsevier B.V. All rights reserved.

关键词： on-line algorithms Competitive analysis Lookahead Traveling salesman problem

来源：评论

学校读者我要写书评

暂无评论

On-line file caching

引用

ALGORITHMICA 2002年第3期33卷 371-383页

作者： Young, NE Dartmouth Coll Hanover NH 03755 USA Akamai Technol Cambridge MA 02138 USA

Consider the following file caching problem: in response to a sequence of requests for files, where each file has a specified size and retrieval cost, maintain a cache of files of total size at most some specified k so as to minimize the total retrieval cost. Specifically, when a requested file is not in the cache, bring it into the cache and pay the retrieval cost, and remove other files from the cache so that the total size of files remaining in the cache is at most k. This problem generalizes previous paging and caching problems by allowing objects of arbitrary Size and cost, both important attributes when caching files for world-wide-web browsers, servers, and proxies. We give a simple deterministic on-line algorithm that generalizes many well-known paging and weighted-caching strategies, including least-recently-used, first-in-first-out, flush-when-full, and the balance algorithm. On any request sequence, the total cost incurred by the algorithm is at most k/(k-h+1) times the minimum possible using a cache of size h less than or equal to k. For any algorithm satisfying the latter bound, we show it is also the case that for most choices of k, the retrieval cost is either insignificant or at most a constant (independent of k) times the optimum. This helps explain why competitive ratios of many on-line paging algorithms have been typically observed to be constant in practice.

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

来源：评论

学校读者我要写书评

暂无评论

Balanced allocations

引用

SIAM JOURNAL ON COMPUTING 1999年第1期29卷 180-200页

作者： Azar, Y Broder, AZ Karlin, AR Upfal, E Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel Digital Syst Res Ctr Palo Alto CA 94301 USA Univ Washington Dept Comp Sci Seattle WA 98195 USA IBM Corp Almaden Res Ctr San Jose CA 95120 USA Weizmann Inst Sci Dept Appl Math IL-76100 Rehovot Israel

Suppose that we sequentially place n balls into n boxes by putting each ball into a randomly chosen box. It is well known that when we are done, the fullest box has with high probability (1 + o(1)) ln n/ ln ln n balls in it. Suppose instead that for each ball we choose two boxes at random and place the ball into the one which is less full at the time of placement. We show that with high probability, the fullest box contains only ln ln n/ ln 2 + O(1) balls-exponentially less than before. Furthermore, we show that a similar gap exists in the infinite process, where at each step one ball, chosen uniformly at random, is deleted, and one ball is added in the manner above. We discuss consequences of this and related theorems for dynamic resource allocation, hashing, and on-line load balancing.

关键词： urn models occupancy problems on-line algorithms resource allocation hashing load balancing

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

On-line extensible bin packing with unequal bin sizes

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2009年第1期11卷 141-152页

作者： Ye, Deshi Zhang, Guochuan Zhejiang Univ Coll Comp Sci Hangzhou 310027 Peoples R China

In the extensible bin packing problem we are asked to pack a set of items into a given number of bins, each with an original size. However, the original bin sizes can be extended if necessary. The goal is to minimize the total size of the bins. We consider the problem with unequal (original) bin sizes and give the complete analysis on a list scheduling algorithm (LS). Namely we present tight bounds of LS for every collection of original bin sizes and every number of bins. We further show better on-line algorithms for the two-bin case and the three-bin case. Interestingly, it is proved that the on-line algorithms have better competitive ratios for unequal bins than for equal bins. Some variants of the problem are also discussed.

关键词： on-line algorithms extensible bin packing competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Competitive deadline scheduling via additional or faster processors

引用

JOURNAL OF SCHEDULING 2003年第2期6卷 213-223页

作者： Koo, CY Lam, TW Ngan, TW To, KK Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

This paper studies on-line scheduling in a single-processor system that allows preemption. The aim is to maximize the total value of jobs completed by their deadlines. It is known that if the on-line scheduler is given a processor faster (say, two times faster) than the off-line scheduler, then there exists an on-line algorithm called SLACKER that can achieve an O(1) competitive ratio. In this paper, we show that using additional unit-speed processors instead of a faster processor is a possible but not cost effective way to achieve an O(1) competitive ratio. Specifically, we find that-Theta(log k) unit-speed processors are required, where k is the importance ratio. Another contribution of this paper is an improved analysis of the competitiveness of SLACKER;this new analysis enables us to show that SLACKER, when extended to multi-processor systems, can still guarantee an O(1) competitive ratio.

关键词： on-line algorithms extra-resource analysis competitiveness deadline scheduling

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：