Indexed by:期刊论文

Date of Publication:2014-06-26

Journal:THEORETICAL COMPUTER SCIENCE

Included Journals:SCIE、EI、Scopus

Volume:540

Issue:,SI

Page Number:62-69

ISSN No.:0304-3975

Key Words:Knapsack problems; Online algorithms; Competitive ratio

Abstract: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.