面向重叠集合族永续监测的公平命中序列调度与近似算法研究

《Discrete Applied Mathematics》：Fair hitting sequence problem

　　

研究人员针对一类新兴的永续调度问题展开研究，即公平命中序列（Fair Hitting Sequence，FHS）问题。给定节点集合 V={v1,…,vn} 与可能相交的集合族 S={S1,…,Sm}，每时刻访问一个节点，凡包含该节点的集合均被视为已被照料；每个集合 Sj 具有增长速率（growth rate）hj>0，其未访问时紧迫性指标（urgency indicator）或称高度（height）以 hj 线性累积，访问后归零。目标是构造无限序列，使任意集合在所有访问间隔内高度上确界的最小化，即调度高度 Height(A) 最优。该问题推广了经典命中集（Hitting Set）问题与竹园修剪（bamboo garden trimming）及 pinwheel 调度。研究人员证明 FHS 为 NP-hard，并基于多命中集分层与分数松弛（fractional relaxation）给出确定性 O(log2 m) 近似及随机化 O(log m) 高概率近似算法，同时推导任意调度高度的下界。

研究背景与问题提出

在重叠社区监测、社交网络信息分发与多传感网络访问等场景中，网络由若干可能重叠的子集构成，访问任一子集中的单个节点即可“命中”该子集。传统永续调度多关注节点级固定频率访问，而现实需求要求按子集差异化紧迫程度持续覆盖。已有竹园修剪与 pinwheel 调度未充分处理“集合相交、命中即覆盖、异构成长速率”的公平性问题。由于 FHS 在均匀速率下退化为最小命中集问题，而最小命中集与集合覆盖均为 NP-hard，且对数近似存在计算困难壁垒，因此亟需可高效构造的近似调度理论。

研究人员开展的工作与结论

研究人员形式化定义 FHS 问题，以调度高度 Height(A) 为优化目标，证明最优周期调度存在性，并建立 FHS 与命中集、顶点覆盖、分数规划的关联。核心结论为：单一最小命中集调度在成长速率差异大时近似比可劣至 Θ(m/log m)；通过按 h_j 分层求近似命中集可得确定性 O(log² m) 近似；进一步借助线性规划下界与随机化方法，可获得 O(log m) 高概率近似；同时构造紧实例说明分层算法 log m 损失不可避免。

主要关键技术方法

研究人员采用四类方法：一，将集合族按成长速率 h_j 做二分式分层，对各层独立求 D-近似命中集（Hitting Set）并交织调度；二，利用贪心命中集保证多项式时间内的 O(log m) 集合规模近似；三，建立分数版 FHS 的线性规划（LP）松弛，以变量 x_i 表示节点被访问的时间占比，推导最优高度下界 X_opt；四，基于分数解设计随机化调度，使高度以高概率控制在 O(log m)·X_opt 内。

研究结果

1. 2.
   确定性 O(log² m) 近似调度
   2.1 基于单一命中集的算法：在 h_max/h_min 有界时，最小命中集循环调度为 C-近似；结合贪心命中集得 O((log m)·h_max/h_min) 近似。
   2.2 单一最小命中集的低效性：构造节点 c 与链状集合实例，显示最小命中集忽略高覆盖度节点，导致近似比至少 m/(2 log m)。
   2.3 多命中集算法：将集合分为 k_max=?log m?+1 层，各层取近似命中集 W_k，交替执行 A(W_k)；证明整体为 O(D log m) 近似，取贪心 D=O(log m) 即得 O(log² m) 近似。
   2.4 多命中集紧例：二叉树状集合族显示即便用最优分层命中集，算法仍可能 Θ(log m) 倍偏离最优。
2. 3.
   基于分数解的下界
   研究人员截取前 T 个时隙，以 z_i 为节点访问频率，推导集合 S_j 高度不低于 h_jT/(I(j,T)+1)，并等价转化为线性规划 (P)：最小化 X，满足 Σx_i=1 且每集合覆盖量 ≥ h_j/X。证明任意调度 Height(A) ≥ X_opt，从而将组合调度问题锚定到分数松弛最优值。
3. 4.
   随机化 O(log m) 近似
   基于第3节分数下界，研究人员设计随机算法利用最优分数解采样节点序列，使调度高度以高概率为 O(log m)·X_opt，逼近理论可行界。
4. 5.
   讨论与结论
   讨论部分指出 FHS 统一了命中集、永续监控与频率公平访问，分层与分数松弛是处理异构成长速率的关键。作者结论为：FHS 天然 NP-hard；确定性算法可达 O(log² m)，随机化可达 O(log m) 高概率近似；下界由分数 LP 给出且紧实例存在；未来可延伸至连续空间、多智能体与动态集合族。研究意义在于为重叠网络监测提供了可证明高效的调度框架与复杂度边界。

结论译文

研究人员得出结论：公平命中序列问题将经典命中集嵌入永续频率调度，其最优高度可由分数线性规划刻画下界；通过分层命中集可实现多项式时间 O(log² m) 确定近似，通过分数解随机化可实现 O(log m) 高概率近似，且相关对数因子在构造实例中不可改进。该工作为重叠社区与传感网络的公平持续访问奠定了组合优化基础。

你想先把这篇解读改写成期刊审稿意见，还是会议论文精炼摘要？

审稿意见

会议摘要

审稿意见

会议摘要