《連通與設施選址問題的近似算法研究》是依託北京工業大學，由徐大川擔任項目負責人的面上項目。
基本介紹
- 中文名：連通與設施選址問題的近似算法研究
- 項目類別：面上項目
- 項目負責人：徐大川
- 依託單位：北京工業大學
項目摘要,結題摘要,
項目摘要
隨著經濟的發展, 信息的及時性和準確性顯得尤為重要, 因此網路中的連通性研究對實際套用有著深遠的影響, 而網路設計中的大部分問題都是NP困難的, 近似算法是研究這類問題的重要方法之一. 斯坦納樹是網路連通結構中最基本的一類結構, 在超大規模積體電路(VLSI), 無線網路等領域中都有廣泛的套用. 而設施選址問題也是計算機科學和運籌學中的一類基本問題, 起源於工廠, 倉庫等位置的確定, 在現代社會的基站設計, 網路伺服器代理的安置中也有廣泛的套用. 但隨著網路結構越來越複雜, 單點對之間的連通已經不能夠滿足生產需求. 本項目在斯坦納樹問題和設施選址問題的基礎上, 從近似算法的角度研究將連通性與設施選址問題相結合的問題- - 連通設施選址問題及其推廣形式. 設計近似算法時需要用到下面的技巧, 線性規劃捨入或隨機捨入(尤其是引入服從非均勻分布的隨機參數), 原始對偶, 對偶擬合, 和局部搜尋等.
結題摘要
本項目圍繞網路設計中具有深刻現實意義的NP-難問題，從近似算法角度進行研究。研究的問題主要包括設施選址問題，斯坦納樹問題，圖劃分問題，半定規劃和魯棒最佳化等, 均取得了預期研究成果。並且在研究上述問題過程中很好地將不同問題的算法設計技巧相融合，對後續研究提供了更多的思路和啟發。在本項目支持下共發表期刊論文26篇(其中SCI檢索論文17篇)，會議論文9篇。 隨著科學技術的發展，信息的及時性、準確性和大數據性扮演的角色日益重要，在以前的研究中認為切合實際的模型變得日益遠離實際。本項目對當今科技水平下的諸多現實問題抽象出了更加貼切也更加廣義的模型，在前人研究技巧上加以創新和推廣，提出了我們的新型近似算法。 我們研究了帶線性和次模懲罰的設施選址問題，將此前的最好近似比1.8526和2.5分別改進到了1.5148和2。論文被中國、美國、波蘭、荷蘭、巴西、日本等多國學者引用28次，其中包括麻省理工學院Retsef Levi、哥倫比亞大學Adam N. Elmachtoub、弗羅茨瓦夫大學Jaroslaw Byrka等，該結果迄今為止仍未被改進。我們提出和研究了帶懲罰的一般設施選址問題並設計了其7.88-近似算法, 隨後此結果被我們改進到了5.83。 此外, 我們研究了多階段設施選址問題，隨機設施選址問題，容錯設施選址問題，平方度量設施選址問題和k-設施選址問題等。斯坦納樹問題上，我們主要研究了其獎勵收集模型，分別設計了廣義獎勵收集斯坦納森林問題的原始對偶近似算法和獎勵收集的k-斯坦納樹問題的5-近似算法。 在算法設計的技巧研究方面，我們得到了魯棒最佳化的分散式機會約束的安全近似，最小化次模函式和半定捨入設計近似算法方面的部分結果. 作為技巧的延伸，我們還研究了圖劃分和無關機排序的部分變形問題。
