多目标集合覆盖问题的标量化方法与近似算法研究：理论突破与应用前景

《Journal of Computational Science》：Exploring scalarization methods and approximation algorithms for the Multi-Objective Set Covering Problem

本文系统综述了多目标集合覆盖问题（MOSCP）这一NP难组合优化问题的研究进展。作者重点分析了加权求和（weighted-sum）与加权最大排序（weighted max-ordering）两种标量化方法在统一权重向量框架下的性能对比，提出了基于成本效益向量（cost-effectiveness vector）的新型近似算法，并建立了logm近似理论保证。通过四种权重生成策略的实证研究，验证了加权最大排序标量化在生成两阶段算法初始解集方面的优势，为多目标组合优化（MOCO）领域提供了新的算法设计范式。

　　

Further insights and new developments

本节我们通过执行算法1对MOSCP进行深入分析。需注意在算法任意迭代步骤中，未覆盖项目包含在S_l^*∩ (E\ē)中（其中l∈L）。当S_l^*中所有项目被覆盖时，S_l^*∩ (E\ē) = ?。现在考虑覆盖某个项目e_k的迭代步骤：令S_j^*为本轮覆盖e_k所选集合，α_j^*为该集合的成本效益向量。对于S_l^*∈ S^*且 α_l= [α_l¹,…,α_l^p]^T，其成本效益特性将直接影响近似解的质量。

Numerical performances

本部分通过计算实验评估提出方法的有效性。实验设计旨在验证：跨标量化方法的统一权重向量策略优势、基于log_m近似算法的解质量、以及从成本效益向量推导的理论性质。通过与现有方法对比，凸显了在近似质量和计算效率方面的显著提升。

Summary, conclusion and future research directions

本研究针对计算复杂的MOSCP问题进行了系统性探索。文献综述发现现有六项研究主要聚焦启发式、元启发式和局部搜索近似算法，仅有一项研究涉及具有理论误差保证的近似方法。我们的核心贡献在于提出了能够有效求解MOSCP的创新方法框架。