时间：2015年11月19日（周四）9：45
地点：仓山校区成功楼603报告厅
主讲：香港大学 张涌副研究员
主办：福建省网络安全与密码技术重点实验室、数学与计算机科学学院
专家简介：张涌博士，1998年毕业于复旦大学电子工程系，获学士学位；2007年，毕业于复旦大学计算机系，获博士学位。2004-2007年在香港大学任职研究助理，2007年在德国柏林工业大学数学系做博士后，2008年至今香港大学任职副研究员。长期从事组合优化、算法设计与分析领域的研究工作，近年来，发表学术论文超过60篇，绝大部分被SCI、EI索引。近期主要研究包括复杂网络，在线优化，图算法。
报告摘要：A seller has L units of product to be sold to a sequence σ of buyers u1, u2, . . . , uσ arriving online and he needs to decide, for each ui, the amount of product to be sold to ui at the then-prevailing market price pi. The objective is to maximize the seller’s revenue. All previous algorithms for the problem need to impose some artificial upper bound M and lower bound m on the market prices, and the seller needs to know either the values of M and m, or their ratio M/m, at the outset.
In this talk, we give an algorithm that does not impose any bounds on market prices and whose performance guarantee depends directly on the input. In particular, we give a class of algorithms such that for any positive integer h and any positive number ?, we have an algorithm Ah,? with good competitive ratio. We also prove that our algorithms are near optimal by showing that given any positive integer h and any algorithm A, we can construct a sequence of buyers σ such that the ratio between the optimal revenue and the revenue obtained by A is lower bounded by some value which is very close to the upper bound.
Moreover, a new model for online pricing -- supply model, is considered. In this model, the seller not only set prices to the items, but can set the amount of items to each user. Again, the objective is to maximize the seller's revenue. We consider two variants, single-type of items and multi-type of items. Both upper bounds and lower bounds are given. model for online pricing -- supply model, is considered. In this model, the seller not only set prices to the items, but can set the amount of items to each user. Again, the objective is to maximize the seller's revenue. We consider two variants, single-type of items and multi-type of items. Both upper bounds and lower bounds are given.