Advertisement
Published in:
2017 | OriginalPaper | Chapter
Online Knapsack Problem Under Concave Functions
Authors : Xin Han, Ning Ma, Kazuhisa Makino, He Chen
Published in: Frontiers in Algorithmics
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
In this paper, we address an online knapsack problem under concave function f(x), i.e., an item with size x has its profit f(x). We first obtain a simple lower bound \(\max \{q, \frac{f'(0)}{f(1)}\}\), where \(q \approx 1.618\), then show that this bound is not tight, and give an improved lower bound. Finally, we find the online algorithm for linear function [8] can be employed to the concave case, and prove its competitive ratio is \(\frac{f'(0)}{f(1/q)}\), then we give a refined online algorithm with a competitive ratio \(\frac{f'(0)}{f(1)} +1\). And we also give optimal algorithms for some piecewise linear functions.