Study On The Online Pricing Problem Of One Kind Of Items With Budgets

This thesis mainly concerns design and analysis of approximation algorithms for the online pricing problem of one kind of items with budgets.For each problem studied in this paper,both online approximation algorithms and the competitive ratio are provided.The online pricing problem of one kind of items with budgets meas that the seller has a certain amount of items which can be sold fractionally.When a user arrives,the seller should make decisions based on user's budgets and bids.The decisions are that the items' price to the user and the number of items allocated.The goal is to maximize the revenue of the seller,which the sum of money paid by all users.The online pricing problem of one kind of items with budgets can be applied in the fields of computer bandwidth allocation and cloud resources,and is close to reality.At the same time,these issues have important theoretical significance.This thesis is split up into five chapters.We first introduced some preliminary concepts and necessary knowledge about algorithms,summarizes of the related research status and the model of the pricing problem in chapter one.In the second chapter,we study the online pricing problem with public budget when the maximum bid can be known in advance.An approximate algorithm is designed and the competitive ratio of the algorithm is analyzed.When B?m/[logh]+1,the competitive ratio is 2;when m/[log h]+1<B<hm,the competitive ratio is max{O(log(B log h)),O(log h)};when B ? hm1 the competitive ratio is O(log h).In the third chapter,we study the online pricing problem with two different types of budgets when the maximum bid can be known in advance.In order to solve this problem,an approximate algorithm is designed.The impact of different budget sizes on the algorithm competition ratio is discussed.When B1<B2 ?m/[log h]+1,the competitive ratio is 2;when B1 ? m/[log h]+1<hm ? B2,the competitive ratio is O(h([log h]+ 1));whenB1?m/[log h]+1<B2<hm,the competitive ratio is O(([log h]+1)B2/B1 when m/[log h]+1<B1<B2<hm,the competitive ratio is max{O(B2/B1 log(B1log h)),O(log h)};when m/[log h]+1<Bi<hm ? B2,the competitive ratio is O(h(log h + 1));when hm<B1<B2,the competitive ratio is O(log h)?When the maximum bid isn't known in advance,online pricing problem with the budget which is studied in the fourth chapter by using the hierarchical method is different from the previous two chapters.Then use it to design algorithms and analysis algorithm of competitive ratio:when B<m,the competitive ratio is 2h2/(?);when B>m,competitive ratio is max{O(Bh1/(?)),O(h3/()>)}.The last part of the paper is the summary and discusses the further research directions of the related issues,especially the promotion of the one kind of items to many kinds of items.