Fair hitting sequence problem

Given a set V=v1,…,vn of n elements and a family S=S1,S2,…,Sm of (possibly intersecting) subsets of V, we consider a scheduling problem involving the perpetual monitoring (or attending) of these subsets. At each time step, one element of V is visited, and all subsets in S containing that element are considered attended during that step. Each subset Sj is assigned an urgency factor hj, which reflects how frequently it should be attended relative to other subsets. Let ti(j) denote the time slot when subset Sj is attended for the ith time. The goal is to devise a perpetual schedule for visiting the elements of V that minimizes the maximum value of hj(ti+1(j)−ti(j)). 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 hj 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 S into sub-families and combines hitting sets for these sub-families, achieving O(log2m)-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 O(logm)-approximate schedules.