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 𝑂 ⁡ ( l o g 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 𝑂 ⁡ ( l o g ⁡ 𝑚 ) -approximate schedules.