Improved Online Algorithm for Fractional Knapsack in the Random Order Model

Giliberti, Jeff; Karrenbauer, Andreas

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Paper

Improved Online Algorithm for Fractional Knapsack in the Random Order Model

MPS-Authors

Giliberti, Jeff
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44737

Karrenbauer, Andreas
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

arXiv:2109.04428.pdf
(Preprint), 212KB

Supplementary Material (public)

There is no public supplementary material available

Citation

Giliberti, J., & Karrenbauer, A. (2021). Improved Online Algorithm for Fractional Knapsack in the Random Order Model. Retrieved from https://arxiv.org/abs/2109.04428.

Cite as: https://hdl.handle.net/21.11116/0000-0009-B637-C

Abstract

The fractional knapsack problem is one of the classical problems in
combinatorial optimization, which is well understood in the offline setting.
However, the corresponding online setting has been handled only briefly in the
theoretical computer science literature so far, although it appears in several
applications. Even the previously best known guarantee for the competitive
ratio was worse than the best known for the integral problem in the popular
random order model. We show that there is an algorithm for the online
fractional knapsack problem that admits a competitive ratio of 4.39. Our result
significantly improves over the previously best known competitive ratio of 9.37
and surpasses the current best 6.65-competitive algorithm for the integral
case. Moreover, our algorithm is deterministic in contrast to the randomized
algorithms achieving the results mentioned above.