《新型計算環境下的排序問題》是依託浙江大學，由張國川擔任項目負責人的面上項目。
基本介紹
- 中文名：新型計算環境下的排序問題
- 依託單位：浙江大學
- 項目負責人：張國川
- 項目類別：面上項目
項目摘要,結題摘要,
項目摘要
排序問題是組合最佳化領域的一個非常活躍的分支。近年來新的計算環境為排序提出了重要挑戰。綠色計算、多核計算、雲計算和服務計算中出現了大量的排序模型，包括能耗有效的排序問題、帶加速資源的排序問題、路由排序問題和博弈環境下的排序算法機制設計問題。在這些模型中排序起著至關重要的作用。本項目立足於這種非傳統計算環境下的排序問題，研究額外約束對排序效能的影響，刻畫最優解結構的變化，拓展算法手段，挖掘新的算法思想。特別地，我們將關注能耗與排序目標的依賴關係；考察加速資源下離線和線上算法的設計與分析；突破帶到達時間的網路路由排序的平凡上界； 討論博弈環境下機器的排序機制和機器/工件共同博弈的納什均衡存在性和效率分析。爭取重要算法成果。
結題摘要
排序問題是組合最佳化近似算法和線上算法研究的重要模型之一。經過五十年來的三個不同階段深入研究，經典的極小化最大完工時間的排序模型仍遺留了若干關鍵的算法理論問題，包括同型機精確算法和多項式近似方案、無關機2-近似算法以及平行機線上算法的改進等。項目組從全新的視角去研究這些經典問題，取得了重要成果。在指數時間假設下，我們給出了同型機精確算法與多項式近似方案的時間複雜度下界，從而表明目前已有的算法結果已經無法改進。這是排序問題算法時間複雜度下界的突破性成果。主要結果發表於ACM-SIAM的算法旗艦會議SODA（2014）上；對於無關機，我們深入研究了工件加工時間矩陣的秩與算法近似比的內在關係。眾所周知，當秩為1，該問題有多項式近似方案；當秩為2的時候，存在擬多項式近似方案。而在一般情形下，不存在近似比小於3/2的多項式時間算法（除非P=NP）。我們證明了當秩為3 時，該問題是APX-困難的，即不存在多項式近似方案，在秩為4時，3/2這個近似比的下界已經成立（除非P=NP）。這些深刻的結果基本上刻畫了在秩作為參數的情況下該問題的複雜性框架，回答了SODA（2013）會議論文上的公開問題。平行機線上排序自Graham的LS算法以來一直是線上算法領域的核心問題，我們在競爭比近似方案的框架下給出了該問題的一簇線上算法，其可以無限逼近最優的線上算法，在新的算法設計思想下，極大地拓展了已有的結果（SODA 2013）。 除了經典困難問題的新方法外，我們還深入研究了有強烈實際背景的各類與排序相關的組合最佳化問題。當機器有容量限制時，我們提出了全新的算法技巧，設計了有效多項式近似方案，在指數時間假設下，其時間複雜度幾乎不可再改進。該論文獲得了第十屆國際組合最佳化及其套用會議的最佳論文。當機器具有加速資源時，該問題成為無關機排序的更一般情況。我們設計了2-近似算法。而當機器數或者資源數目為給定常數時，則給出了多項式近似方案。我們提出了成組元素的背包問題，依賴於元素尺寸與背包總容量之比的參數，完整刻畫了算法的上下界。 此外，本項目還著手探討了若干與博弈相關的組合最佳化模型，取得了有趣的結果。 截止目前，項目組已發表標註論文12篇。
