香港大学张涌副研究员学术报告  11月19日上午

发布时间:2015-11-13浏览次数:255

报告人:张涌副研究员  香港大学

  

报告题目:On the Power and Limitation of Algorithmic Analysis for Online Pricing

  

时  间:20151119 (星期四) 09:45

  

地  点:仓山校区成功楼603报告厅

  

主  办:福建省网络安全与密码技术重点实验室,数学与计算机科学学院

  

参加对象:计算机系教师、研究生

  

报告摘要: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 sellers 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.

  

专家简介:张涌博士1998年毕业于复旦大学电子工程系,获学士学位;2007年,毕业于复旦大学计算机系,获博士学位。2004年至2007年在香港大学任职研究助理,2007年在德国柏林工业大学数学系做博士后,2008年至今于香港大学任职副研究员。张涌博士长期从事组合优化,算法设计与分析方面的研究工作,近年来在本领域的一些国际著名会议和期刊上发表科研论文超过60篇,绝大部分被SCIEI索引。近期的主要研究工作包括复杂网络,在线优化,图算法等。