線上背包問題的相關模型和算法分析

《線上背包問題的相關模型和算法分析》是依託大連理工大學,由韓鑫擔任醒目負責人的青年科學基金項目。

基本介紹

• 中文名：線上背包問題的相關模型和算法分析
• 依託單位：大連理工大學
• 項目類別：青年科學基金項目
• 項目負責人：韓鑫

項目摘要

背包問題是經典的組合最最佳化問題之一，傳統的背包問題只能解決事先給出物品信息的資源調配，而近幾年線上背包問題是背包問題研究領域的重要分支之一。該理論對於解決現實生活中非確定條件下資源的分配有著重要的意義，比如網路套用中的關鍵字拍賣，廣告顯示等。本項目工作重點是研究線上背包的相關模型和算法分析，包括提出線上背包的五個新模型，即線上凸，凹，有償，遞增，遞減背包模型，設計近似比（競爭比）為常數的線上算法並分別給出可行性分析，討論相應模型線上算法競爭比的下界等。項目的目標是使得線上算法的近似比跟各自問題的下界儘量接近，以至於吻合。最後考慮進一步推廣利用所提出的線上算法來解決在網路時代中新湧現的其它線上問題。

結題摘要

該項目所研究的線上背包問題, 是組合最佳化, 計算機理論,運籌領域中比較基本的問題，在網路關鍵字拍賣等有著重要套用。 三年來，本人對立項中的線上背包問題取得以下主要結果： 1：對於有償線上背包問題，我們找到了一個上屆和下屆一致的線上算法，文章發表在國際重要期刊Algorithmica 2014; 2: 對於帶凸函式線上背包問題，我們給出了一個上屆世5/3的線上算法，文章發表在國際重要期刊Theoretical Computer Science 2014; 3：對於二維的背包問題，我們要給出近似比為1+\eps的快速近似算法，文章發表在Theoretical Computer Science 2013; 4:對於帶凹函式的背包問題，我們給出上屆和下屆差是1的線上算法，文章正在投稿中。 因為背包問題和裝箱問題，還有調度問題，它們之間有著很好的相關性，除了對線上背包問題的研究之外，我們也有計畫外的產物，具體如下： 1：對三維strip packing問題,我們給出近似比為1.69103的漸進近似算法，該比值是目前最好的比值，文章發表在國際頂級期刊 SIAM Journal on computing2013； 2：對二維線上裝箱問題我們給出了競爭比為2.55的線上算法，該算法也是目前最好的算法，文章發表在在國際頂級期刊ACM Transactions on Algorithms 2011； 3：另外對線上排序問題進行了研究，在Theoretical Computer Science，Information Processing Letters等期刊上發表了數篇文章。 總體上我們很好完成了立項中的問題，同時也額外的取得了計畫外的結果。共發表SCI檢索期刊文章13篇, EI檢索文章20篇。 同時獲得了2014年中國運籌學會的青年科技獎的提名獎。