报告题目1：Single machine controllable sche****ng with bounded makespan

报告人：罗文昌教授，宁波大学

报告时间：2025年5月12日（周一）9:00-10:00

报告地点：20-200

报告摘要：In a recent controllable sche****ng environment, the processing time of a job can be shortened by allocating extra resource at a cost, or a job can be declined for processing by paying a penalty. We investigate the single machine controllable sche****ng to minimize the sum of the total resource consumption cost, the total job rejection cost, and the makespan of the accepted jobs, where the makespan is upper bounded and the job processing time is a decreasing linear function in the amount of allocated resource. We first show that the studied problem is polynomial solvable if the makespan is unbounded, but otherwise is NP-hard, and characterize important structural properties for the optimal solution; we then take advantage of the structural properties to design several algorithms for the problem, including a pseudo-polynomial time dynamic programming exact algorithm, a 3-approximation algorithm based on linear programming and rounding, a fast O(n2)-time n-approximation algorithm where n is the number of jobs, and building on top of the dynamic programming exact algorithm and the n-approximation algorithm, a fully polynomial time approximation scheme.

报告人简介：罗文昌，宁波大学数学与统计学院教授，博士生导师。于2011年6月获浙江大学运筹学博士学位。已完成教育部项目及浙江省自然科学基金项目，国家自然科学基金面上项目各1项，目前主持国家自然科学基金面上项目1项，已在Algorithmica，JOS，EJOR，OMEGA，JORS等主流国际期刊及ISSAC，COCOON等主流国际学术会议发表SCI/EI/SSCI检索论文40余篇。近5年来，指导本科生参加全国大学生数学建模竞赛获得国家级一、二等奖项十余项；指导本科生参加美国大学生数学建模竞赛获F奖、M奖及H奖十余项；指导研究生参加全国研究生数学建模竞赛获国家级一、二及三等奖十余项。

报告题目2：Improved approximation algorithms for the k^+-star packing problem

报告人：张安教授，杭州电子科技大学

报告时间：2025年5月12日（周一）10:00-11:00

报告地点：20-200

报告摘要：For a positive integer k≥1, a k-star (k^+-star) is a connected graph containing a degree-l vertex and l degree-1 vertices, where l=k (l≥k). The k^+-star packing problem is to cover as many vertices of an input graph G as possible using vertex-disjoint k^+-stars in G. The problem is strongly NP-hard for any fixed k≥2. We present a (1+(k+1)/3-1/3(k+1) +ϵ)- and a 4/3-approximation algorithms for the k^+-star packing problem when k≥3 and k=2, respectively, both improving our previous approximation results on this problem.

报告人简介：张安，杭州电子科技大学教授、博士生导师。2009年6月在浙江大学运筹学与控制论方向获得博士学位（导师为姚恩瑜教授和谈之奕教授）。现为中国运筹学会理事，中国运筹学会数学规划分会和排序分会理事。主要研究组合优化理论与算法、数学建模及其应用等。主持3项国家自然科学基金、3项浙江省自然科学基金以及1项中国博士后基金。在Inf. Comput., Algorithmica, Eur. J. Oper. Res., Discrete Appl. Math., Theor. Comput. Sci., 中国运筹学会会刊等国内外期刊上发表40余篇论文。研究成果曾获得浙江省高等学校科研成果奖二等奖。

邀请人：张昭