Campus Event Calendar
Event Entry
What and Who
Improved Online Algorithm for Fractional Knapsack in the Random Order Model
Jeff Giliberti
Department of Computer Science, ETH Zurich
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 26 August 2021
13:00
30 Minutes
Virtual talk
Virtual talk
Saarbrücken
Abstract
The fractional knapsack problem is one of the classical problems in combinatorial optimization, which is well understood in the offline setting. The corresponding online setting has been handled only briefly in the theoretical computer science literature so far, although it appears in several applications. In this talk, I present an algorithm for the online fractional knapsack problem in the popular random order model that admits a competitive ratio of 4.39. This 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.
This talk is based on joint work with Andreas Karrenbauer.
--------
Join Zoom Meeting
Meeting ID: 527 278 8807
Note: For people outside D1 interested in listening to this talk, please contact Roohani Sharma at rsharma@mpi-inf.mpg.de for the password.
Contact
Roohani Sharma
Virtual Meeting Details
Zoom
527 278 8807
public
Roohani Sharma, 08/26/2021 01:59
Roohani Sharma, 08/23/2021 07:42
Roohani Sharma, 08/21/2021 10:42
Roohani Sharma, 08/20/2021 19:20 -- Created document.
Roohani Sharma, 08/23/2021 07:42
Roohani Sharma, 08/21/2021 10:42
Roohani Sharma, 08/20/2021 19:20 -- Created document.