2 papers
cs.DS2026
A Tight Information-Theoretic Lower Bound for Randomized Online Set Cover
Ilan Doron-Arad, Joseph, Naor
Online set cover is a fundamental problem in online algorithms, admitting a deterministic -competitive algorithm, where is the number of sets and is the nu…
cs.DS2024
Non-Linear Paging
Ilan Doron-Arad, Joseph, Naor
We formulate and study non-linear paging - a broad model of online paging where the size of subsets of pages is determined by a monotone non-linear set function of the pages. This…