最大多重覆蓋問題的近似演算法

Abstract

集合覆蓋問題（Set Cover Problem, SCP）是一個經典的 NP-困難組合優化問題，具有重要的理論與實務價值。其變體如最大覆蓋與多重覆蓋問題，透過加入額外的約束與覆蓋需求，擴展了問題的應用範圍。我們的工作聚焦於線性上的多重覆蓋問題，目標是在有限點數下選擇點集，以最大化區間的完整多重覆蓋。此問題與兩個主要領域密切相關：資訊擴散領域—其中基於獨立級聯模型（Independent Cascade Model）與線性閾值模型（Linear Threshold Model）的基礎研究，促使影響力最大化與選舉控制等課題獲得廣泛關注；以及幾何最大覆蓋領域，此領域區間與圓盤覆蓋問題上擁有強大的近似演算法與多項式時間求解法，應用範圍涵蓋設施選址、影像處理等。這些連結啟發我們研究連結兩者的廣義最大多重覆蓋問題。 本文針對最大點多重覆蓋問題（Maximum Points Multi-Cover, MPMC）處理三個主要議題。首先，對於區間重疊情形下的 MPMC 問題，我們提出了一種可達成全多項式時間近似方案（FPTAS）的演算法。其次，在排序區間的 MPMC問題中，我們設計出一個多項式時間演算法，能達到 1/2 的近似保證。最後，針對一般的 MPMC 問題，我們設計了一個多項式時間演算法，其近似比可達(1−1/e)/2f−1，其中 f 表示所有區間中的最大覆蓋需求。

The Set Cover Problem (SCP) is a classic NP-hard combinatorial optimization prob- lem with significant theoretical and practical applications. Variants such as maximum coverage and multi-cover extend its scope by incorporating additional constraints and coverage requirements. Our work focuses on the multi-cover problem on a line, aiming to select limited points to maximize full multi-coverage of intervals. This problem is closely related to two key domains: information diffusion—where foundational models like the Independent Cascade and Linear Threshold models have spurred extensive research on influence maximization and election control—and geometric maximum coverage, a field with strong approximation results and polynomial-time algorithms for problems involving interval and disk coverage, with applications ranging from facility location to image processing. These connections motivate our study of generalized maximum multi-coverage problems bridging both areas. In this paper, we address three main problems related to the Maximum Points Multi-Cover (MPMC) problem. First, we consider the MPMC problem on overlapping intervals. We propose an algorithm that yields a Fully Polynomial-Time Approximation Scheme (FPTAS) for this setting.Second, we study the MPMC problem on sorted intervals. For this case, we develop a polynomial-time algorithm that achieves a 1/2-approximation guarantee.Third, we tackle the general MPMC problem by designing a polynomial-time algorithms.the algorithm achieves an approximation ratio to (1−1/e)/(2f−1), where f denotes the maximum coverage requirement among all intervals.