|
个人信息Personal Information
教授
博士生导师
硕士生导师
主要任职：Professor
性别：男
毕业院校：日本京都大学
学位：博士
所在单位：软件学院、国际信息与软件学院
学科：计算机软件与理论. 运筹学与控制论
联系方式：hanxin@dlut.edu.cn
Online removable knapsack problem under convex function
点击次数：
论文类型：期刊论文
发表时间：2014-06-26
发表刊物：THEORETICAL COMPUTER SCIENCE
收录刊物：SCIE、EI、Scopus
卷号：540
期号：,SI
页面范围：62-69
ISSN号：0304-3975
关键字：Knapsack problems; Online algorithms; Competitive ratio
摘要：In this paper, we address an online knapsack problem under a convex size profit function. We first give a greedy online algorithm with a competitive ratio 2. Then we propose an improved online algorithm with a competitive ratio 5/3. We also prove that when the convex function has a specific property, our improved online algorithm is (1 + root 5)/2-competitive, which is optimal. Finally, we prove that the lower bound of this problem is (1 + root 5)/2. (C) 2013 Elsevier B.V. All rights reserved.