- 學位論文
以演算法的角度探討區域及全域資源分配
An Algorithmic Approach to Local and Global Resource Allocations
摘要
在這份學位論文裡，我們從演算法的角度來考慮資源分配問題。 在具有區域限制條件的資源分配問題裡，資源只能在相鄰的物件之間被配置； 而在全域資源分配裡，資源則可以被包裝、藉由中繼轉運點由來源地被運送到目的地。對於區域資源分配以及全域資源運用這兩大類問題，我們分別提出了抽象化的數學模型、能透過理論被證明的良好演算方法、以及問題困難度的證明，藉以譜出對於這個複雜議題的一份完整而全面的研究。 在區域性的需求供給方面，我們考慮了一個支配集問題在``衍生'這個概念底下的推廣問題。 我們稱之為``有容量的支配集問題'。首先，在不預設任何條件的一般圖形上，我們提出了能與傳統支配集問題的近似演算法相匹配、且以無窮漸近的角度來看是最佳的近似演算法。 除此之外，在一些圖形集合，例如：樹、樹寬度有上限的圖形、以及平面圖等之上，一系列的困難度證明，指出了我們所考慮的這個問題，在本質上比傳統支配集問題更為困難與複雜。 除了困難度的證明之外，對於這些圖形的集合，我們也提出了相對應的近似演算方法。 在全域的資源運用方面，作為研究複雜全域分配最佳化的起始橋樑，我們首先考慮無迴圈的子網路建構及維護問題。 在這個問題裡，我們希望這個無迴圈的子網路，在以距離作為加權的平均度量底下，能夠良好地保持與原本差距不大的距離空間。 對於建構及維護這樣的子網路，我們分別提出了有效率並且具有良好理論保證的演算方法。接著，我們進一步將每個連接所需的花費及效能納入考量，在最大化投資報酬率的概念底下，研究``最佳花費與效能比例'的子網路建構問題。 在這個議題底下，針對不同的參數要求、以及不同的結構條件限制，我們做了一個全面性的討論與研究。
並列摘要
This dissertation addresses resource allocation from an algorithmic perspective. Starting from resource allocations with locality constraints, in which resource assignments are valid only between adjacent objects, to global resource planning for which the resources can be packed and delivered via intermediate stops to demanding targets, we present algorithmic results with solid theoretical guarantees as well as hardness proofs to jointly compose a comprehensive study for the entire problem. In terms of local demand supplying, we consider a generalization of the dominating set problem under the concept of capacitataion, namely, the capacitated domination problem. On one hand, approximation algorithms matching the classical bounds for the dominating set problem which are proven to be optimal in an asymptotic sense are presented for general graphs. On the other hand, a series of hardness results for trees, graphs of bounded treewidths, and planar graphs is presented to show that the considered problem is fundamentally more difficult than the extensively-studied dominating set problem, whereas corresponding approximation algorithms for these three graph classes are also provided. In terms of global resource planning, as an initiative step to the intricate global optimization, we first consider the construction and maintenance problem of acyclic networks which well-preserve the distance metric of the original space in a distance-weighted average sense. Efficient algorithms with quality guarantees for both problems are presented. Second, taking the expense and the impact of each link construction into consideration, we consider the problem of cost-efficient network construction, in the sense of maximizing the return of investments. A comprehensive study regarding different parametric requirements and structural constraints is presented.