Algorithms for Timely Bin Packing, Fair TCP Acknowledgement, and Variants

Abstract

The Timely Bin Packing problem is a variant of bin packing, which incorporates time constraints for packing items. This is related to the classic Dynamic TCP Acknowledgement problem, which has been extensively studied and has real-world applications. This thesis studies new algorithms and settings for these two related problems.

For Timely Bin Packing, we present deterministic and randomized algorithms that improve the best-known competitive ratios. We further provide impossibility results for different settings and variants of the problem. We also study the problem under certain assumptions, such as having restricted sizes and integer arrival times.

For Dynamic TCP Acknowledgement, we study relaxed settings that include machine-learned predictions. We consider the fmax objective, which balances the max-latency of acknowledged packets (thus conveying a notion of max-min fairness). For this setting, we study learning-augmented algorithms and present experimental results on both synthetic and real-world data.