“优化与应用”前沿讲座.docVIP

“优化与应用”前沿讲座 时间：2010.7.31-8.1 地点：思源楼一层大报告厅 主办：数学院“优化与应用”研究中心 7月31日下午学术报告（2：00开始） 报告题目：An Analysis of Serial Allocation Rule in Group Buying 报告者：Jiawei Zhang （张家伟） 报告者单位：New York University Abstract: When a seller offers quantity discount, buyers can aggregate their purchasing quantity to obtain lower prices. A cost allocation rule determines how much each buyer would pay for the amount they they purchased. Various cost allocation rules have been used in practice. Different allocation rules may have may different influence on the buyers behavior (i.e., their purchasing quantities) In this paper, we study the serial allocation rule and analyze the equilibrium purchasing quantity under this rule. 报告题目：Approximation algorithms for the facility location problems with linear/submodular penalties 报告者：徐大川 报告者单位：北京工业大学 Abstract: We study two variants of the classical \emph{facility location problem} (FLP), namely the \emph{facility location problem with linear penalties} (FLPLP) and the \emph{facility location problem with submodular penalties} (FLPSP). Our main contribution is to provide greatly improved approximation algorithms for both problems via several novel techniques which exploit the special properties of the linear/submodular penalty function. For the former problem, our LP-rounding based non-combinatorial $1.575$-approximation algorithm offers the currently best approximation ratio (the currently best combinatorial approximation ratio is $1.853$ due to Xu and Xu \cite{xx2}). For the latter problem, our LP-rounding based $2.056$-approximation algorithm and the primal-dual with greedy argumentation based $2.375$-approximation algorithm offer the currently best non-combinatorial and combinatorial approximation ratios, respectively. Moreover, we also give the first verifiable dual-fitting based approximation algorithms for both problems. Joint work with Yu Li, Donglei Du, and Naihua Xiu. 报告题目：Sparse Signal Reconstruction via Iterative Supp