集合裝箱及集合覆蓋問題之研究

Abstract

裝箱 (Bin packing) 和覆蓋 (bin covering) 是資源規劃中常見的兩個重要問題。兩者都是把一個集合內的元素依照某些限制條件或目標函數來做分組。在傳統的裝箱和覆蓋問題中，分組的元素通常是物件的純量屬性，如價格、重量、或體積等。本論文將純量元素推廣至子集合，亦即每個元素本身就是一個集合。有別於純量元素，子集合的聯集運算是次可加的(subadditive)。而且聯集的基數 (cardinality) 是最具代表性的模集函數 (submodular set function) 之一。在此，我們在一貫性的架構下，界定出四類裝箱和覆蓋問題，並對各類問題以實際的應用範例加以解說。由於這些問題本身都是NP-hard，我們提出一個通用的貪婪式 (Greedy) 演算法策略，對各類問題發展出近似演算法，並分析其 approximation ratio(近似精準率) 。

Bin packing and bin covering are two of the most commonly arising computational tasks in resource allocation. Both problems aim to partition a set of items abiding by some constraints to achieve specific objectives. This work provides a unifying framework to deal with bin packing and bin covering for various constraints and objectives. Mostly, we focus on the study of the coverage of subsets, which is one of the most commonly addressed submodular functions. The thesis identifies several related problems of interests and proposes approximations with perfomance guarantees.