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

Randomized algorithms for online knapsack problems

THEORETICAL COMPUTER SCIENCE 2015年第C期562卷 395-405页

作者： Han, Xin Kawase, Yasushi Makino, Kazuhisa Dalian Univ Technol Software Sch Dalian Peoples R China Tokyo Inst Technol Dept Social Engn Tokyo Japan Kyoto Univ Math Sci Res Inst Kyoto 6068501 Japan

In this paper, we study online knapsack problems. The input is a sequence of items e(1), e(2), ..., e(n), each of which has a size and a value. Given the ith item e(i), we either put ei into the knapsack or reject it. In the removable setting, when ei is put into the knapsack, some items in the knapsack are removed with no cost if the sum of the size of ei and the total size in the current knapsack exceeds the capacity of the knapsack. Our goal is to maximize the profit, i.e., the sum of the values of items in the last knapsack. We present a simple randomized 2-competitive algorithm for the unweighted non-removable case and show that it is the best possible, where knapsack problem is called unweighted if the value of each item is equal to its size. For the removable case, we propose a randomized 2-competitive algorithm despite there is no constant competitive deterministic algorithm. We also provide a lower bound 1 + 1/e approximate to 1.368 for the competitive ratio. For the unweighted removable case, we propose a 10/7-competitive algorithm and provide a lower bound 1.25 for the competitive ratio. (C) 2014 Elsevier B.V. All rights reserved.

关键词： online algorithm Competitive analysis Randomized algorithm Knapsack problem

来源：评论

学校读者我要写书评

暂无评论

Multistage online maxmin allocation of indivisible entities

引用

THEORETICAL COMPUTER SCIENCE 2022年 933卷 104-113页

作者： Cheng, Sin-Wing HKUST Dept Comp Sci & Engn Hong Kong Peoples R China

We consider an online allocation problem that involves a set Pof nplayers and a set E of m indivisible entities over discrete time steps 1, 2,..., tau. At each time step t is an element of[1, tau], for every entity e is an element of E, there is a restriction list L-t(e) that prescribes the subset of players to whom ecan be assigned and a non-negative value v(t)(e, p) of eto every player p is an element of P. The sets P and E are fixed beforehand. The sets L-t(.) and values v(t)(.,.) are given in an online fashion. An allocation is a distribution of E among P, and we are interested in the minimum total value of the entities received by a player according to the allocation. In the static case, it is NP-hard to find an optimal allocation the maximizes this minimum value. On the other hand, rho-approximation algorithms have been developed for certain values of rho is an element of(0, 1]. We propose a w-lookahead algorithm for the multistage online maxmin allocation problem for any fixed w >= 1 in which the restriction lists and values of entities may change between time steps, and there is a fixed stability reward for an entity to be assigned to the same player from one time step to the next. The objective is to maximize the sum of the minimum values and stability rewards over the time steps 1, 2,..., tau. Our algorithm achieves a competitive ratio of (1 - c)rho, where cis the positive root of the equation wc(2) = rho (w + 1)(1 - c). When w = 1, it is greater than rho/4 rho+2 + rho/10, which improves upon the previous ratio of rho/4 rho+2-2(1-t)(2 rho+1) obtained for the case of 1-lookahead. (c) 2022 Elsevier B.V. All rights reserved.

关键词： online algorithm Maxmin allocation Stability reward

来源：评论

学校读者我要写书评

暂无评论

online batch scheduling with kind release times and incompatible families to minimize makespan

引用

OPTIMIZATION LETTERS 2018年第2期12卷 301-310页

作者： Li, Wenjie Li, Shisheng Feng, Qi Luoyang Normal Univ Sch Math Sci Luoyang 471022 Henan Peoples R China Zhongyuan Univ Technol Dept Informat & Computat Sci Zhengzhou 450007 Henan Peoples R China

This paper studies online scheduling of jobs with incompatible families on a single unbounded batch machine under the KRT environment, where jobs arrive over time and "KRT" means that in the online setting no jobs can be released when the machine is busy. The goal is to determine a feasible schedule to minimize the makespan. We provide a best online algorithm with a competitive ratio of , where f is the number of job families.

关键词： Scheduling online algorithm Kind release time Incompatible families Makespan

来源：评论

学校读者我要写书评

暂无评论

online Scheduling with Known Arrival Times

引用

MATHEMATICS OF OPERATIONS RESEARCH 2009年第1期34卷 92-102页

作者： Hall, Nicholas G. Posner, Marc E. Potts, Chris N. Ohio State Univ Dept Management Sci Columbus OH 43210 USA Ohio State Univ Dept Integrated Syst Engn Columbus OH 43210 USA Univ Southampton Sch Math Southampton SO17 1BJ Hants England

We consider an online scheduling environment where decisions are made without knowledge of the data of jobs that may arrive later. However, additional jobs can only arrive at known future times. This environment interpolates between the classical offline and online scheduling environments and approaches the classical online environment when there are many equally spaced potential job arrival times. The objective is to minimize the sum of weighted completion times, a widely used measure of work-in-process inventory cost and customer service. For a nonpreemptive single machine environment, we show that a lower bound on the competitive ratio of any online algorithm is the solution of a mathematical program. This lower bound is between (1 + SQRT (5))/2 and 2, with the exact value depending on the potential job arrival times. We also provide a "best possible" online scheduling algorithm and show that its competitive ratio matches this lower bound. We analyze two practically motivated special cases where the potential job arrival times have a special structure. When there are many equally spaced potential job arrival times, the competitive ratio of our online algorithm approaches the best possible competitive ratio of 2 for the classical online problem.

关键词： machine scheduling online algorithm total weighted completion time competitive analysis

来源：评论

学校读者我要写书评

暂无评论

How to Allocate Goods in an online Market?

引用

algorithmICA 2016年第2期74卷 589-601页

作者： Azar, Yossi Buchbinder, Niv Jain, Kamal Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel Tel Aviv Univ Stat & Operat Res Dept IL-69978 Tel Aviv Israel eBay Res Labs San Jose CA USA

We study an online version of linear Fisher market. In this market there are buyers and a set of dividable goods to be allocated to the buyers. The utility that buyer derives from good is . Given an allocation in which buyer has utility we study a quality measure that is based on taking an average of the ratios with respect to any other allocation . Market equilibrium allocation is the optimal solution with respect to this measure. Our setting is online and so the allocation of each good should be done without any knowledge of the upcoming goods. We design an online algorithm for the problem that is only worse by a logarithmic factor than any other solution with respect to this quality measure, and in particular competes with the market equilibrium allocation. We prove a tight lower bound which shows that our algorithm is optimal up to constants. Our algorithm uses a primal dual convex programming scheme. To the best of our knowledge this is the first time that such a scheme is used in the online framework.

关键词： online algorithm Allocation Social welfare Fairness Market equilibrium

来源：评论

学校读者我要写书评

暂无评论

online Trajectory and Resource Optimization for Stochastic UAV-Enabled MEC Systems

引用

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2022年第7期21卷 5629-5643页

作者： Yang, Zheyuan Bi, Suzhi Zhang, Ying-Jun Angela Chinese Univ Hong Kong Dept Informat Engn Hong Kong Peoples R China Shenzhen Univ Coll Elect & Informat Engn Shenzhen 518060 Peoples R China Peng Cheng Lab Shenzhen 518066 Peoples R China

The recent development of unmanned aerial vehicle (UAV) and mobile edge computing (MEC) technologies provides flexible and resilient computation services to mobile users out of the terrestrial computing service coverage. In this paper, we consider a UAV-enabled MEC platform that serves multiple mobile ground users with random movements and task arrivals. We aim to minimize the average weighted energy consumption of all users subject to the average UAV energy consumption and data queue stability constraints. We formulate the problem as a multi-stage stochastic optimization, and adopt Lyapunov optimization to convert it into per-slot deterministic problems with fewer optimizing variables. We design two reduced-complexity methods that solve the resource allocation and the UAV movement either in two sequential steps or jointly in one step. Both methods can guarantee to satisfy the average UAV energy and queue stability constraints, meanwhile achieving a tradeoff between the user energy consumption and the length of queue backlog. Simulation results show that the two methods significantly outperform the other benchmark methods including a learning-based method in reducing the energy consumption of ground users. In between, the proposed joint optimization method achieves better performance than the two-stage method at the cost of higher computational complexity.

关键词： Autonomous aerial vehicles Trajectory Wireless communication Task analysis Resource management Energy consumption Computational modeling Unmanned aerial vehicle (UAV) mobile edge computing user mobility stochastic data arrivals Lyapunov optimization online algorithm

来源：评论

学校读者我要写书评

暂无评论

A tight analysis of Brown-Baker-Katseff sequences for online strip packing

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2013年第2期26卷 333-344页

作者： Kern, W. Paulus, J. J. CQM BV NL-5600 AK Eindhoven Netherlands

We study certain adversary sequences for online strip packing which were first designed and investigated by Brown, Baker and Katseff (Acta Inform. 18:207-225) and determine the optimal competitive ratio for packing such Brown-Baker-Katseff sequences online. As a byproduct of our result, we get a new lower bound of for the competitive ratio of online strip packing.

关键词： online algorithm Strip packing Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

online scheduling on an unbounded parallel-batch machine and a standard machine to minimize makespan

引用

INFORMATION PROCESSING LETTERS 2014年第4期114卷 179-184页

作者： Fu, Ruyan Tian, Ji Yuan, Jinjiang Li, Ya China Univ Min & Technol Coll Sci Xuzhou 221116 Jiangsu Peoples R China Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Henan Peoples R China

We consider the online scheduling on an unbounded parallel-batch machine and a standard machine to minimize makespan. In the problem, the jobs arrive online over time and to be processed on two machines M-1 and M-2. M-1 is an unbounded parallel-batch machine and M-2 is a standard machine. The objective is to minimize the makespan, i.e., the maximum completion time of all jobs. For this problem, we present an online algorithm of competitive ratio 5+root 5/4 approximate to 1.809. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Scheduling online algorithm Makespan Parallel batch machine

来源：评论

学校读者我要写书评

暂无评论

online scheduling of a single machine to minimize total weighted completion time

引用

MATHEMATICS OF OPERATIONS RESEARCH 2004年第3期29卷 686-697页

作者： Anderson, EJ Potts, CN Univ New S Wales Australian Grad Sch Management Sydney NSW 2052 Australia Univ Southampton Sch Math Southampton SO17 1BJ Hants England

This paper considers the online scheduling of a single machine in which jobs arrive over time, and preemption is not allowed. The goal is to minimize the total weighted completion time. We show that a simple modification of the shortest weighted processing time rule has a competitive ratio of two. This result is established using a new proof technique that does not rely explicitly on a lower bound on the optimal objective function value. Because it is known that no online algorithm can have a competitive ratio of less than two, we have resolved the open issue of determining the minimum competitive ratio for this problem.

关键词： scheduling single machine total weighted completion time online algorithm competitive ratio

来源：评论

学校读者我要写书评

暂无评论

On the power of lookahead in online lot-sizing

引用

OPERATIONS RESEARCH LETTERS 2010年第6期38卷 522-526页

作者： Ahlroth, Lauri Schumacher, Andre Haanpaa, Harri Aalto Univ Sch Sci & Technol Dept Informat & Comp Sci FI-00076 Aalto Finland Aalto Univ Sch Sci & Technol Dept Commun & Networking FI-00076 Aalto Finland

We propose an online algorithm for an economic lot-sizing (ELS) problem with lookahead, which achieves asymptotically optimal worst-case performance for increasing lookahead. Although intuitive, this result is interesting since deterministic algorithms for previously studied online ELS problems have unbounded competitive ratio. We also prove lookahead-dependent lower bounds for deterministic algorithms. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Competitive analysis online algorithm Lookahead Lot-sizing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：