אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

In this lecture, we study knapsack problems with departures under the online with a sample model. We begin with the fundamental special case of the Temp Secretary Problem with departures, where we obtain a constant competitive ratio of 1/8, providing the first performance guarantee for general instances of this problem.

We then extend our approach to the d-dimensional Online Vector Generalized Assignment Problem with Departures (VGAPWD), achieving a competitive ratio of 1/(16d) for d-dimensional resources. Lastly, we study the Multiple Knapsack Problem With Departures, which is a special case of VGAP.

For this special case, we present a more practical modification of our algorithm that achieves the same competitive ratio. Using extensive simulations on workloads derived from real cluster traces, we demonstrate that our algorithms consistently outperform state of the art algorithms and widely used heuristics, achieving typical improvements of 10–25% in total value compared to state of the art approaches.

These results demonstrate that the online with a sample paradigm successfully translates into algorithms that leverage historical data for improved empirical performance. This is aligned with the stronger theoretical guarantees we can prove within this framework.