帶預(yù)算的單商品在線定價問題研究.pdf

1、本文比較系統(tǒng)地研究了帶預(yù)算的單商品在線定價問題，主要涉及近似算法設(shè)計與競爭比分析。對不同情景下的在線定價問題，設(shè)計了相應(yīng)的近似算法并給出了它們的競爭比。帶預(yù)算的單商品在線定價問題是指賣家有一定量的可分商品賣給用戶，當(dāng)一個用戶到達時，賣家要根據(jù)用戶的預(yù)算和出價等信息做出決定:給出當(dāng)前用戶的商品單價和分配的商品數(shù)量，目標(biāo)函數(shù)是最大化賣家收入。帶預(yù)算的單商品在線定價問題可運用于計算機帶寬分配、云資源等領(lǐng)域，貼近實際，同時這些問題有著重要的理論

2、意義。
　　全文共分為五章，前一章主要介紹了與算法設(shè)計相關(guān)的概念及預(yù)備知識，總結(jié)了定價問題的相關(guān)研究現(xiàn)狀及其模型。
　　第二章研究了最大出價已知時，帶公共預(yù)算的在線定價問題。對此問題設(shè)計出近似算法和分析算法的競爭比。當(dāng)B≤m/([)log h」+1時，競爭比為2;當(dāng)m/([)log h」+1＜B＜hm時，競爭比為max{O(log(B log h)），O(log h)};當(dāng)B≥hm時，競爭比為O(log h)。
　　第

3、三章研究了最大出價能夠提前知道時，帶兩類不同預(yù)算的在線定價問題。針對此問題設(shè)計出了近似算法。討論了不同的預(yù)算大小對算法競爭比的影響。當(dāng)B1＜B2≤m/([)log h」+1時，競爭比是2;當(dāng)B1≤m/([)log h]+1＜hm≤B2時，競爭比是O(h(([)log h]+1)）;當(dāng)B1≤m/([)log h」+1＜B2＜hm時，競爭比是O(([)logh」+1)B2/B1）;當(dāng)m/([)log h」+1＜B1＜B2＜hm時，競爭比為m

4、ax{O(B2/B1log(B1log h))，O(log h)};當(dāng)m/([)log h」+1＜B1＜hm≤B2時，競爭比是O(h(logh+1));當(dāng)hm＜B1＜B2時，競爭比為O(log h)。
　　第四章研究了最大出價不能提前知道時，帶預(yù)算的商品在線定價問題，采用了不同于前面兩章的價格形式進行分層，從而設(shè)計算法和分析算法的競爭比:當(dāng)B≤m，競爭比是2h2/√log h;當(dāng)B＞m，競爭比是max{O(Bh1/√log h)，