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

Improved online algorithms for Knapsack and GAP in the Random Order Model

ALGORITHMICA 2021年第6期83卷 1750-1785页

作者： Albers, Susanne Khan, Arindam Ladewig, Leon Tech Univ Munich Dept Comp Sci Boltzmannstr 3 D-85748 Garching Germany Indian Inst Sci Dept Comp Sci & Automat Bangalore 560012 Karnataka India

The knapsack problem is one of the classical problems in combinatorial optimization: Given a set of items, each specified by its size and profit, the goal is to find a maximum profit packing into a knapsack of bounded capacity. In the online setting, items are revealed one by one and the decision, if the current item is packed or discarded forever, must be done immediately and irrevocably upon arrival. We study the online variant in the random order model where the input sequence is a uniform random permutation of the item set. We develop a randomized (1/6.65)-competitive algorithm for this problem, outperforming the current best algorithm of competitive ratio 1/8.06 (Kesselheim et al. in SIAM J Comput 47(5):1939-1964, 2018). Our algorithm is based on two new insights: We introduce a novel algorithmic approach that employs two given algorithms, optimized for restricted item classes, sequentially on the input sequence. In addition, we study and exploit the relationship of the knapsack problem to the 2-secretary problem. The generalized assignment problem (GAP) includes, besides the knapsack problem, several important problems related to scheduling and matching. We show that in the same online setting, applying the proposed sequential approach yields a (1/6.99)-competitive randomized algorithm for GAP. Again, our proposed algorithm outperforms the current best result of competitive ratio 1/8.06 (Kesselheim et al. in SIAM J Comput 47(5):1939-1964, 2018).

关键词： online algorithms Random order model Packing problems

来源：评论

学校读者我要写书评

暂无评论

Near Optimal online algorithms and Fast Approximation algorithms for Resource Allocation Problems

引用

JOURNAL OF THE ACM 2019年第1期66卷 1-41页

作者： Devanur, Nikhil R. Jain, Kamal Sivan, Balasubramanian Wilkens, Christopher A. Microsoft Res 1 Microsoft Way Redmond WA 98052 USA Faira 608 State St S Kirkland WA 98033 USA Google Res 111 8th Ave New York NY 10011 USA Facebook Res 1 Hacker Way Menlo Pk CA 94025 USA

We present prior robust algorithms for a large class of resource allocation problems where requests arrive one-by-one (online), drawn independently from an unknown distribution at every step. We design a single algorithm that, for every possible underlying distribution, obtains a 1 - epsilon fraction of the profit obtained by an algorithm that knows the entire request sequence ahead of time. The factor epsilon approaches 0 when no single request consumes/contributes a significant fraction of the global consumption/contribution by all requests together. We show that the tradeoff we obtain here that determines how fast epsilon approaches 0, is near optimal: We give a nearly matching lower bound showing that the tradeoff cannot be improved much beyond what we obtain. Going beyond the model of a static underlying distribution, we introduce the adversarial stochastic input model, where an adversary, possibly in an adaptive manner, controls the distributions from which the requests are drawn at each step. Placing no restriction on the adversary, we design an algorithm that obtains a 1 - epsilon fraction of the optimal profit obtainable w.r.t. the worst distribution in the adversarial sequence. Further, if the algorithm is given one number per distribution, namely the optimal profit possible for each of the adversary's distribution, then we design an algorithm that achieves a 1 - epsilon fraction of the weighted average of the optimal profit of each distribution the adversary picks. In the offline setting we give a fast algorithm to solve very large linear programs (LPs) with both packing and covering constraints. We give algorithms to approximately solve (within a factor of 1 + epsilon) the mixed packing-covering problem with O(gamma m log(n/delta)/epsilon(2)) oracle calls where the constraint matrix of this LP has dimen- sion n x m, the success probability of the algorithm is 1 - delta, and gamma quantifies how significant a single request is when compared to the sum tot

关键词： online algorithms unknown distribution approximation algorithms greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

Temperature aware online algorithms for minimizing flow time

引用

THEORETICAL COMPUTER SCIENCE 2017年 661卷 18-34页

作者： Birks, Martin Fung, Stanley P. Y. Univ Leicester Dept Informat Leicester LE1 7RH Leics England

We consider the problem of minimizing the total flow time of a set of unit sized jobs in a discrete time model, subject to a temperature threshold. Each job has its release time and its heat contribution. At each time step the temperature of the processor is determined by its temperature at the previous time step, the job scheduled at this time step and a cooling factor. We show a number of lower bound results, including the case when the heat contributions of jobs are only marginally larger than a trivial threshold. Then we consider a form of resource augmentation by giving the online algorithm a higher temperature threshold, and show that the Hottest First algorithm can be made 1-competitive, while other common algorithms like Coolest First cannot. Finally we give some results in the offline case. (C) 2016 Elsevier B.V. All rights reserved.

关键词： online algorithms Scheduling Temperature Flow time

来源：评论

学校读者我要写书评

暂无评论

Adding isolated vertices makes some greedy online algorithms optimal

引用

DISCRETE APPLIED MATHEMATICS 2018年 246卷 12-21页

作者： Boyar, Joan Kudahl, Christian Univ Southern Denmark Dept Math & Comp Sci Campusvej 55 DK-5230 Odense M Denmark

An unexpected difference between online and offline algorithms is observed. The natural greedy algorithms are shown to be worst case online optimal for online INDEPENDENT SET and online VERTEX COVER On graphs with "enough" isolated vertices, Freckle Graphs. For online DOMINATING SET, the greedy algorithm is shown to be worst case online optimal on graphs with at least one isolated vertex. These algorithms are not online optimal in general. The online optimality results for these greedy algorithms imply optimality according to various worst case performance measures, such as the competitive ratio. It is also shown that, despite this worst case optimality, there are Freckle graphs where the greedy independent set algorithm is objectively less good than another algorithm. It is shown that it is NP-hard to determine any of the following for a given graph: the online independence number, the online vertex cover number, and the online domination number. (C) 2017 Elsevier B.V. All rights reserved.

关键词： online algorithms Greedy algorithm Isolated vertices online independence number

来源：评论

学校读者我要写书评

暂无评论

Approximation and online algorithms for multidimensional bin packing: A survey

引用

COMPUTER SCIENCE REVIEW 2017年 24卷 63-79页

作者： Christensen, Henrik I. Khan, Arindam Pokutta, Sebastian Tetali, Prasad Univ Calif San Diego San Diego CA 92103 USA USI SUPSI Ist Dalle Molle Studi Sull Intelligenza Artificia Lugano Switzerland Georgia Inst Technol Atlanta GA 30332 USA

The bin packing problem is a well-studied problem in combinatorial optimization. In the classical bin packing problem, we are given a list of real numbers in (0, 1] and the goal is to place them in a minimum number of bins so that no bin holds numbers summing to more than 1. The problem is extremely important in practice and finds numerous applications in scheduling, routing and resource allocation problems. Theoretically the problem has rich connections with discrepancy theory, iterative methods, entropy rounding and has led to the development of several algorithmic techniques. In this survey we consider approximation and online algorithms for several classical generalizations of bin packing problem such as geometric bin packing, vector bin packing and various other related problems. There is also a vast literature on mathematical models and exact algorithms for bin packing. However, this survey does not address such exact algorithms. In two-dimensional geometric bin packing, we are given a collection of rectangular items to be packed into a minimum number of unit size square bins. This variant has a lot of applications in cutting stock, vehicle loading, pallet packing, memory allocation and several other logistics and robotics related problems. In d-dimensional vector bin packing, each item is a d-dimensional vector that needs to be packed into unit vector bins. This problem is of great significance in resource constrained scheduling and in recent virtual machine placement in cloud computing. We also consider several other generalizations of bin packing such as geometric knapsack, strip packing and other related problems such as vector scheduling, vector covering etc. We survey algorithms for these problems in offline and online setting, and also mention results for several important special cases. We briefly mention related techniques used in the design and analysis of these algorithms. In the end we conclude with a list of open problems. (C) 2016 Elsevier Inc. A

关键词： Approximation algorithms online algorithms Multidimensional packing and covering Bin packing Multidimensional scheduling Geometric packing

来源：评论

学校读者我要写书评

暂无评论

Optimal search and one-way trading online algorithms

引用

ALGORITHMICA 2001年第1期30卷 101-139页

作者： El-Yaniv, R Fiat, A Karp, RM Turpin, G Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel Int Comp Sci Inst Berkeley CA 94704 USA Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA Univ Toronto Dept Comp Sci Toronto ON M5S 1A4 Canada

This paper is concerned with the time series search and one-way trading problems. In the (time series) search problem a player is searching for the maximum (or minimum) price in a sequence that unfolds sequentially, one price at a time. Once during this game the player can decide to accept the current price p in which case the game ends and the player's payoff is p. In the one-way trading problem a trader is given the task of trading dollars to yen. Each day, a new exchange rate is announced and the trader must decide how many dollars to convert to yen according to the current rate. The game ends when the trader trades his entire dollar wealth to yen and his payoff is the number of yen acquired. The search and one-way trading are intimately related. Any (deterministic or randomized) one-way trading algorithm can be viewed as a randomized search algorithm. Using the competitive ratio as a performance measure we determine the optimal competitive performance for several variants of these problems. In particular, we show that a simple threat-based strategy is optimal and we determine its competitive ratio which yields, for realistic values of the problem parameters, surprisingly low competitive ratios. We also consider and analyze a one-way trading game played against an adversary called Nature where the online player knows the probability distribution of the maximum exchange rate and that distribution has been chosen by Nature. Finally, we consider some applications for a Special case of portfolio selection called two-way trading in which the trader may trade back and forth between cash and one asset.

关键词： time series search one-way trading two-way trading portfolio selection online algorithms competitive analysis

来源：评论

学校读者我要写书评

暂无评论

A Comparison of Performance Measures for online algorithms

引用

ALGORITHMICA 2015年第4期72卷 969-994页

作者： Boyar, Joan Irani, Sandy Larsen, Kim S. Univ Southern Denmark Dept Math & Comp Sci DK-5230 Odense M Denmark Univ Calif Irvine Dept Comp Sci Irvine CA 92697 USA

This paper provides a systematic study of several proposed measures for online algorithms in the context of a specific problem, namely, the two server problem on three colinear points. Even though the problem is simple, it encapsulates a core challenge in online algorithms which is to balance greediness and adaptability. We examine Competitive Analysis, the Max/Max Ratio, the Random Order Ratio, Bijective Analysis and Relative Worst Order Analysis, and determine how these measures compare the Greedy Algorithm, Double Coverage, and Lazy Double Coverage, commonly studied algorithms in the context of server problems. We find that by the Max/Max Ratio and Bijective Analysis, Greedy is the best of the three algorithms. Under the other measures, Double Coverage and Lazy Double Coverage are better, though Relative Worst Order Analysis indicates that Greedy is sometimes better. Only Bijective Analysis and Relative Worst Order Analysis indicate that Lazy Double Coverage is better than Double Coverage. Our results also provide the first proof of optimality of an algorithm under Relative Worst Order Analysis.

关键词： online algorithms K-server problem Performance measures

来源：评论

学校读者我要写书评

暂无评论

Optimal online algorithms for minimax resource scheduling

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2003年第4期16卷 555-590页

作者： Hunsaker, B Kleywegt, AJ Savelsbergh, MWP Tovey, CA Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA

We consider a very general online scheduling problem with an objective to minimize the maximum level of resource allocated. We find a simple characterization of an optimal deterministic online algorithm. We develop further results for the two, more specific problems of single resource scheduling and hierarchical line balancing. We determine how to compute optimal online algorithms for both problems using linear programming and integer programming, respectively. We show that randomized algorithms can outperform deterministic algorithms, but only if the amount of work done is a nonconcave function of resource allocation.

关键词： online algorithms competitive analysis worst-case analysis single-machine scheduling multiprocessor scheduling line balancing

来源：评论

学校读者我要写书评

暂无评论

Optimal online algorithms for File-Bundle Caching and Generalization to Distributed Caching

引用

ACM TRANSACTIONS ON MODELING AND PERFORMANCE EVALUATION OF COMPUTING SYSTEMS 2021年第1期6卷 1–23页

作者： Qin, Tiancheng Etesami, S. Rasoul Univ Illinois Dept Ind & Syst Engn 104 S Mathews Ave Urbana IL 61801 USA Univ Illinois Dept Ind & Syst Engn Coordinated Sci Lab 104 S Mathews Ave Urbana IL 61801 USA

We consider a generalization of the standard cache problem called file-bundle caching, where different queries (tasks), each containing l >= 1 files, sequentially arrive. An online algorithm that does not know the sequence of queries ahead of time must adaptively decide on what files to keep in the cache to incur the minimum number of cache misses. Here a cache miss refers to the case where at least one file in a query is missing among the cache files. In the special case where l = 1, this problem reduces to the standard cache problem. We first analyze the performance of the classic least recently used (LRU) algorithm in this setting and show that LRU is a near-optimal online deterministic algorithm for file-bundle caching with regard to competitive ratio. We then extend our results to a generalized (h, k)-paging problem in this file-bundle setting, where the performance of the online algorithm with a cache size k is compared to an optimal offline benchmark of a smaller cache size h < k. In this latter case, we provide a randomized O(l ln k/k-h)-competitive algorithm for our generalized (h, k)-paging problem, which can be viewed as an extension of the classic marking algorithm. We complete this result by providing a matching lower bound for the competitive ratio, indicating that the performance of this modified marking algorithm is within a factor of 2 of any randomized online algorithm. Finally, we look at the distributed version of the file-bundle caching problem where there are m >= 1 identical caches in the system. In this case, we show that for m = l + 1 caches, there is a deterministic distributed caching algorithm that is (l(2) + l)-competitive and a randomized distributed caching algorithm that is O(l ln(2l + 1))-competitive when l >= 2. We also provide a general framework to devise other efficient algorithms for the distributed file-bundle caching problem and evaluate the performance of our results through simulations.

关键词： File-bundle caching generalized (h, k)-paging distributed caching LRU algorithm marking algorithm online algorithms competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Controlling distribution conveyors and multiline palletizers: theoretical foundations and online algorithms

引用

OR SPECTRUM 2019年第2期41卷 581-611页

作者： Gurski, Frank Rehs, Carolin Rethmann, Jochen Wanke, Egon Univ Dusseldorf Inst Comp Sci D-40225 Dusseldorf Germany Niederrhein Univ Appl Sci Fac Elect Engn & Comp Sci D-47805 Krefeld Germany

We consider the Distribution problem for multiline palletizing systems, which arises in centralized distribution centres, where boxes have to be stacked up from conveyor belts onto pallets with respect to customer orders. The problem asks how to distribute boxes to k buffer queues such that an optimal subsequent stacking process requires only p stack-up places. The boxes reach the palletizer on the main conveyor of an order-picking system. A distribution conveyor pushes the boxes out to several buffer conveyors. Robotic arms are placed at the end of these buffer conveyors, where each arm picks up the first box of one of the buffer conveyors and moves it onto a pallet located at one of p stack-up places. In this paper, we seek for an assignment of the boxes from the main conveyor to the buffer conveyors such that only p stack-up places are used during the subsequent stacking process. We present online algorithms and analyse their worst-case behaviour. For restricted problems, an optimal online algorithm is given, which also performs very well for general instances. The average-case behaviour is determined by experiments. For benchmarking the general case, we present two binary integer programs. The Distribution problem for stacking systems has not been investigated up to now, although it is a natural problem to consider.

关键词： Binary integer program Combinatorial optimization Computational complexity online algorithms Palletizing systems Stacking systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：