“优化与应用”前沿讲座 时间：2010.7.31-8.1地点：思源楼一层大报告厅主办：数学院“优化与应用”研究中心7月31日下午学术报告（2：00开始）报告题目：An Analysis of Serial Allocation Rule in Group Buying报告者：Jiawei Zhang （张家伟）报告者单位：New York UniversityAbstract: 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 emphfacility location problem (FLP), namely the emphfacility location problem with linear penalties (FLPLP) and the emphfacility 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 citexx2). 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 Support Detection 报告者：Wotao Yin （印卧涛）报告者单位：Rice UniversityAbstract: We present a novel sparse signal reconstruction method “ISD”, which reconstructs sparse signals faster from a reduced number of measurements compared to the classical L1 minimization. ISD addresses failed reconstructions of L1 minimization due to insufficient measurements. It estimates a support set from a current reconstruction and obtains a new reconstruction by solving a truncated L1 minimization problem, and it iterates these two steps for a small number of times. The talk will include analysis and theoretical justifications of ISD. ISD has been applied to image reconstruction. The resulting code EdgeCS recovers images of higher qualities from fewer measurements than the current state-of-the-art methods. EdgeCS exactly recovers the 256x256 Shepp-Logan phantom from merely 7 radial lines (or 3.03% k-space), which is impossible for most existing algorithms. It accurately reconstructs a 512512 magnetic resonance image from 21% noisy samples. Moreover, it is also able to reconstruct complex-valued images. This is joint work with Weihong Guo (Case Western) and Yilun Wang (Cornell).7月31日下午学术报告（茶歇20分钟以后开始）报告题目：Approximation Algorithm for Polynomial Function Optimization报告者：Simai He (何斯迈)报告者单位：香港中文大学Abstract: We consider polynomial-time approximation algorithms for optimizing a genericmulti-variate homogeneous polynomial function, subject to ellipsoid constraints.Approximation algorithms are proposed for this problem with the proven worst-case relative approximationperformance ratios, which are dependent only on the dimensions of the model.Furthermore, by applying the Lowner-John theorem, the constraint set is relaxed to a general bounded convex set.Results of our numerical experiments are reported, indicating remarkably good performance of the proposed algorithms for solving the randomly generated test instances.The results can be extended for inhomogeneous polynomial function with ellipsoid constraints.报告题目：DEM Constructoin from Contour lines based on Regional Optimum Control 报告者：DunJiang Song(宋敦江)报告者单位：中国科学院科技政策与管理科学研究所Abstract: Digital Elevation Model (DEM) data are widely used in many research areas such as Geographical Information System (GIS), hydrological analysis and soil erosion models. Traditional contour lines from manual interpretation of landforms are an important kind of data source for DEM construction. DEM of scales 1:10,000, 1:50,000 and 1:250,000 from State Bureau of Surveying and Mapping P.R.C are constructed from contour lines and scattered points using the constrained Triangulated Irregular Network (TIN) method. HASM (High Accuracy Surface Modeling) is a method for surface modeling, based on the theory of surface, which means that, except its position in space, a surface is uniquely defined by its first fundamental coefficients and second fundamental coefficients. Presently, HASM is mai