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

On-line models and algorithms for max independent set

RAIRO-OPERATIONS RESEARCH 2006年第2期40卷 129-142页

作者： Escoffier, Bruno Paschos, Vangelis Th. Univ Paris 09 LAMSADE F-75775 Paris 16 France

In on-line computation, the instance of the problem dealt is not entirely known from the beginning of the solution process, but it is revealed step-by-step. In this paper we deal with on-line independent set. On-line models studied until now for this problem suppose that the input graph is initially empty and revealed either vertex-by-vertex, or cluster-by-cluster. Here we present a new on-line model quite different to the ones already studied. It assumes that a superset of the final graph is initially present ( in our case the complete graph on the order n of the final graph) and edges are progressively removed until the achievement of the final graph. Next, we revisit the model introduced in [Demange, Paradon and Paschos, Lect. Notes Comput. Sci. 1963 (2000) 326-334] and study relaxations assuming that some paying backtracking is allowed.

关键词： approximation algorithms competitive ratio maximum independent set on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

On-line competitive algorithms for call admission in optical networks

引用

ALGORITHMICA 2001年第1期31卷 29-43页

作者： Awerbuch, B Azar, Y Fiat, A Leonardi, S Rosén, A Johns Hopkins Univ Baltimore MD 21218 USA MIT Comp Sci Lab Cambridge MA 02139 USA Univ Roma La Sapienza Dipartimento Informat Sistemist I-00198 Rome Italy Univ Toronto Dept Comp Sci Toronto ON M5S 1A4 Canada

We study the on-line call admission problem in optical networks. We present a general technique that allows us to reduce the problem of call admission and wavelength selection to the call admission problem. We then give randomized algorithms with logarithmic competitive ratios for specific topologies in switchless and reconfigurable optical networks. We conclude by considering full duplex communications.

关键词： on-line algorithms competitive analysis optical networks

来源：评论

学校读者我要写书评

暂无评论

Off-line algorithms for the list update problem

引用

INFORMATION PROCESSING LETTERS 1996年第2期60卷 75-80页

作者： Reingold, N Westbrook, J AT&T BELL LABS MURRAY HILLNJ 07974 YALE UNIV DEPT COMP SCINEW HAVENCT 06520

Optimum off-line algorithms for the list update problem are investigated, The list update problem involves implementing a dictionary of items as a linear list. Several characterizations of optimum algorithms are given;these lead to optimum algorithm which runs in time Theta 2(n)(n - 1)!m, where n is the length of the list and m is the number of requests. The previous best algorithm, an adaptation of a more general algorithm due to Manasse et al. (1988), runs in time Theta(n!)(2)m.

关键词： sequential search list update on-line algorithms off-line algorithms competitive analysis analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Dial-a-Ride Problem with Time-Windows and on-line algorithms

Dial-a-Ride Problem with Time-Windows and On-Line Algorithms

引用

中国运筹学会第七届学术交流会

作者： Yi Fanglei Xu Yinfeng School of Management,Xi'an Jiaotong University, Xi'an, 710049

In this paper results on dial-a-ride problem with time-windows are pre-sented. Requests for rides appearing over time consist of two points in a metric space,a source and a *** transport objects of requests from sources to des-tinations. Each request specifies a deadlines. If a request is not be served by itsdeadline, it will be called *** goal is to plan the motion of servers in an on-lineway so that the maximum number of requests is met by their deadline. We performcompetitive analysis of two deterministic strategies for the problem in two cases sep-arately, when the server has finite capacity (z=1) and when the server has infinitecapacity (z =∞). Then we obtain their competitive ratios.

关键词： Logistics Vehicle Scheduling on-line algorithms Competitive Analysis

来源：评论

学校读者我要写书评

暂无评论

Limitations Concerning On-line Scheduling algorithms for Overloaded Real-Time Systems

引用

IFAC Proceedings Volumes 1991年第2期24卷 123-125页

作者： S.K. Baruah L.E. Rosier Department of Computer Sciences The University of Texas at Austin Austin TX 78712-1188 USA

With respect to on-line scheduling algorithms that must direct the service of sporadic task requests we quantify the benefit of possessing knowledge concerning the timing of future events. Consider the problem of preemptively scheduling sporadic task requests in a uniprocessor environment. If a task request is successfully scheduled to completion, a value equal to the request’s execution time is obtained; otherwise a value of zero is obtained. We prove that no on-line scheduling algorithm can guarantee a cumulative value greater than (√2—1) times the value obtainable by a clairvoyant scheduler, i.e., we prove a performance guarantee limitation of 41.4%. Over intervals where the loading factor does not exceed one the performance guarantee limitation is 100%. As the loading factor exceeds one we show that the performance guarantee limitation immediately drops to 61.8%. and as the loading factor increases from one to two, we show that the performance guarantee limitation falls from 61.8%; to 41.4%. Beyond two the performance guarantee limitation remains at 41.4%.

关键词： Real time computer systems scheduling theory on-line algorithms performance bounds optimal performance

来源：评论

学校读者我要写书评

暂无评论

Picking Operations in Warehouses With Dynamically Arriving Orders: How Good is Reoptimization?

引用

NETWORKS 2025年

作者： Lorenz, Catherine Otto, Alena Gendreau, Michel Univ Passau Chair Management Sci Operat & Supply Chain Managem Passau Germany Tech Univ Munich Adv Analyt Mfg Management Heilbronn Germany Polytech Montreal Dept Math & Ind Engn Montreal PQ Canada Polytech Montreal CIRRELT Montreal PQ Canada

E-commerce operations are essentially online, with customer orders arriving dynamically. However, very little is known about the performance of online policies for warehousing with respect to optimality, particularly for order picking and batching operations, which constitute a substantial portion of the total operating costs in warehouses. We aim to close this gap for one of the most prominent dynamic algorithms, namely reoptimization (Reopt), which reoptimizes the current solution each time a new order arrives. We examine Reopt in the Online Order Batching, Sequencing, and Routing Problem (OOBSRP), in both cases when the picker uses either a manual pushcart or a robotic cart. Moreover, we examine the non-interventionist Reopt in the case of a manual pushcart, wherein picking instructions are provided exclusively at the depot. We establish analytical performance bounds employing worst-case and probabilistic analysis. We demonstrate that, under generic stochastic assumptions, Reopt is almost surely asymptotically optimal and, notably, we validate its near-optimal performance in computational experiments across a broad range of warehouse settings. These results underscore Reopt's relevance as a method for online warehousing applications.

关键词： competitive analysis on-line algorithms order batching and routing problem reoptimization warehouses

来源：评论

学校读者我要写书评

暂无评论

ONline algorithms FOR DIVISION AND MULTIPLICATION

引用

IEEE TRANSACTIONS ON COMPUTERS 1977年第7期26卷 681-687页

作者： TRIVEDI, KS ERCEGOVAC, MD UNIV ILLINOIS DEPT COMP SCIURBANAIL 61801

In this paper, on-line algorithms for division and multiplication are developed. It is assumed that the operands as well as the result flow through the arithmetic unit in a digit-by-digit, most significant digit first... 详细信息

关键词： Computer arithmetic division multiplication on-line algorithms pipelining radix redundancy.

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

algorithms for on-line bin-packing problems with cardinality constraints

引用

DISCRETE APPLIED MATHEMATICS 2004年第1-3期143卷 238-251页

作者： Babel, L Chen, B Kellerer, H Kotov, V Graz Univ Inst Stat & Operat Res A-8010 Graz Austria Univ Warwick Warwick Business Sch Coventry CV4 7AL W Midlands England EADS Germany D-5705 Unterschleissheim Germany Univ Minsk Fac Appl Math & Comp Sci Minsk 220080 BELARUS

The bin-packing problem asks for a packing of a list of items of sizes from (0, 1) into the smallest possible number of bins having unit capacity. The k-item bin-packing problem additionally imposes the constraint that at most k items are allowed in one bin. We present two efficient on-line algorithms for this problem. We show that, for increasing values of k, the bound on the asymptotic worst-case performance ratio of the first algorithm tends towards 2 and that the second algorithm has a ratio of 2. Both algorithms considerably improve upon the best known result of an algorithm, which has an asymptotic bound of 2.7 on its ratio. Moreover, we improve known bounds for all values of k by presenting on-line algorithms for k = 2 and 3 with bounds on their ratios close to optimal. (C) 2004 Elsevier B.V. All rights reserved.

关键词： bin packing on-line algorithms cardinality constraint

来源：评论

学校读者我要写书评

暂无评论

algorithms for the on-line Quota Traveling Salesman Problem

引用

INFORMATION PROCESSING LETTERS 2004年第2期92卷 89-94页

作者： Ausiello, G Demange, M Laura, L Paschos, V Univ Roma La Sapienza Dipartimento Informat & Sistemist I-00198 Rome Italy Univ Paris 09 F-75775 Paris 16 France ESSEC Dept SID F-95021 Cergy Pontoise France

The Quota Traveling Salesman Problem is a generalization of the well-known Traveling Salesman Problem. The goal of the traveling salesman is, in this case, to reach a given quota of sales, minimizing the amount of time. In this paper we address the on-line version of the problem, where requests are given over time. We present algorithms for various metric spaces, and analyze their performance in the usual framework of competitive analysis. In particular we present a 2-competitive algorithm that matches the lower bound for general metric spaces. In the case of the halfline metric space, we show that it is helpful not to move at full speed, and this approach is also used to derive the best on-line polynomial time algorithm known so far for the On-line TSP (in the homing version). (C) 2004 Elsevier B.V. All rights reserved.

关键词： on-line algorithms Traveling Salesman Problem Quota TSP

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：