Fair hitting sequence problem

Given a set 𝑉 = 𝑣 1 , … , 𝑣 𝑛 of 𝑛 elements and a family  = 𝑆 1 , 𝑆 2 , … , 𝑆 𝑚 of (possibly intersecting) subsets of 𝑉 , we consider a scheduling problem involving the perpetual monitoring (or attending) of these subsets.At each time step, one element of 𝑉 is visited, and all subsets in  containing that element are considered attended during that step.Each subset 𝑆 𝑗 is assigned an urgency factor ℎ 𝑗 , which reflects how frequently it should be attended relative to other subsets.Let 𝑡 (𝑗) 𝑖 denote the time slot when subset 𝑆 𝑗 is attended for the 𝑖-th time.The goal is to devise a perpetual schedule for visiting the elements of 𝑉 that minimizes the maximum value of ℎ 𝑗 (𝑡 (𝑗) 𝑖+1 -𝑡 (𝑗) 𝑖 ).We refer to this problem as the fair hitting sequence (FHS problem), noting its connection to the minimum hitting set problem.Specifically, in the uniform FHS case, where all urgency factors ℎ 𝑗 are equal, the problem reduces to the minimum hitting set problem, which is NP-hard.We show that schedules based on a single hitting set, even an optimal one, can yield poor approximation ratios.To address this, we propose a deterministic algorithm that partitions the family  into sub-families and combines hitting sets for these sub-families, achieving 𝑂(log 2 𝑚)approximate schedules.Additionally, we establish a lower bound on the optimal objective value of FHS using linear programming (LP) techniques.Leveraging this bound, we develop a randomized algorithm that, with high probability, computes 𝑂(log 𝑚)-approximate schedules.