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

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

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

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

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