Exploring scalarization methods and approximation algorithms for the Multi-Objective Set Covering Problem

doi:10.1016/j.jocs.2026.102785

2026-01-23

PRE

Lakmali Weerasena *

Chathuri Aththanayake

DOI：10.1016/j.jocs.2026.102785

原文链接

原文求助

摘要

En 中文

This study focuses on the Multi-Objective Set Covering Problem (MOSCP), a prominent challenge in Multi-Objective Combinatorial Optimization. Given the NP-completeness of the Set Covering Problem (SCP), both Single Objective SCP (SOSCP) and MOSCP evolve into NP-hard combinatorial optimization problems. Our investigation reveals a gap in the literature, as norm-based scalarizations have been identified as effective in approximating multi-objective minimization problems, yet limited research exists on ϵ-approximation algorithms for the MOSCP. Our contribution unfolds on two fronts: (1) We explore the impact of using a common set of weight vectors for two scalarization methods weighted-sum and weighted max-ordering in solving the MOSCP under various conditions. We integrate four distinct weight computing methods and precisely solve both weighted-sum scalarization and weighted max-ordering scalarization of the MOSCP. (2) We utilize the cost-effectiveness vector proposed in previous literature to extract additional theoretical properties describing the approximation quality. Furthermore, we introduce a new cost-effectiveness vector and discuss its validity in relation to the properties identified in prior studies, resulting in the derivation of new theoretical properties. The study indicates that introduced weight generation methods demonstrate commendable performance with an equivalent number of weight vectors on the MOSCP. Furthermore, employing weighted max-ordering scalarization is proposed as a suitable choice for generating a robust initial pool for two-phase algorithms.