学术会议

组合优化与图论专题研讨会(线上)

发布人:发布时间: 2022-06-14

字体大小: 【小】 【中】 【大】




南京大学 2022 组合优化与图论专题研讨会


         日程安排


时间:2022 6 15-17 日上午 8:30-11:30


方式:腾讯会议 ID447 029 5544        入会密码: 202206


或点击链接入会:  https://meeting.tencent.com/p/4470295544





报告摘要和个人简介


1    2022615号上午 (周三) 报告

主持人:张玉忠教授,曲阜师范大学

个人简介:张玉忠,曲阜师范大学运筹学研究院院长,二级教授,华东师范大学、 曲阜师范 大学博士生导师,中国运筹学会副理事长,排序分会理事长。山东省人大常委。1981– 1988年 曲阜师范学院数学系本科、运筹学研究所硕士。1994– 1997年,中国科学院应用数学研究所博 士,运筹学与控制论专业。主要从事运筹学的研究,上世纪90年代中期在国内最早开展分批排 序问题的研究,用连续优化的理论与方法研究排序问题国内的倡导者和实践者,并建立了学 术团队。发表学术论文300余篇,其中在Algorithmica, Journal of Combinatorial Optimization, Science China等国内外核心刊物上发表100余篇。主持完成国家自然科学基金项目5项。10次获 得教育部、山东省科技进步和教学成果奖。学术团队完成国家课题20余项。 自1995年指导20余 届硕士、10余届博士研究生150余名,多名成长为教授、博士生导师、国家优青、泰山学者。 他是山东省教学名师。2000年继王长钰教授任运筹学研究所所长,2002年创建了管理学院,并 兼任院长至2017年,这期间,创建了5个管理学本科专业,1个一级学科硕士点– 管理科学与工 程。联合数学系、 自动化研究所成功申报了博士点–应用数学,实现了曲师大博士点零的突破。 自2000年至今两届中国运筹学会理事、两届常务理事,第二届中国运筹学会副理事长。《运筹 学学报》、《运筹与管理》编委。山东省第十一、十二、十三届人大常委。其事迹被《光明日 报》、《China Daily》、《中国青年报》等媒体报道。


报告1 (8:30-9:10) :Bike rebalancing: find a balanced matching in the k-center problem 报告人:张国川教授,浙江大学计算机科学与技术学院

报告摘要:In this talk, we will revisit the mid rush rebalancing problem in the bike sharing system proposed by O’Mahony and Shmoys (2015), which brings the matching constraints to the k-center problem. Given a graph G = (U, V, E) in a metric space, where |U | = |V |, we aim to compute k (positive) centers for points in U, and k (negative) centers for points in V. The k centers for U should be perfectly matched with the k centers for V , within an allowed distance. The goal is to minimize the maximum distance from each point in U  (or in V) to its closest centers in U  (or in V).  The model is motivated by the real-world application in rebalancing bikes. However, the model did not capture the balanced feature between two matched centers. To fix this issue, we add an exact capacity restriction to each center in the mid rush rebalancing problem. Namely, all centers must serve the same number of bikes, so that the matched centers are balanced.  We design a 9-approximation algorithm, which is built on the technique called transfer-preserving network that successfully combines the approach for the capacitated k-center problem by An et al.  (2015) with the technique for the mid rush rebalancing problem.  Joint with Jinxiang Gan and Yuhao Zhang

个人简介:张国川,浙江大学教授。1995 年在中科院应用数学所获得运筹学博士学位。 曾先 后在格拉茨工业大学和浙江大学做博士后。2001 年获得洪堡基金。研究兴趣包括组合优化和算法博弈论。国际会议ISAAC 顾问委员会委员,COCOON 指导委员会委员。  (曾) 担任国际 期刊Journal of Scheduling, International Journal of Foundations of Computer Science, Parallel Computing, OMEGA 等期刊编委。


报告2 (9:10-9:50) :博弈排序与局部搜索算法

报告人:李荣珩教授,湖南师范大学数学与统计学院

报告摘要:博弈排序近年来是排序的热点研究之一,局部搜索算法是优化算法中常用的近似算 法,我们将说明博弈排序的纳什均衡与局部最优的相互关系,并对这方面的模型及其近似分析 成果进行简要介绍。

个人简介:李荣珩,博士,湖南师范大学数学与统计学院教授,研究方向为组合优化方面的 算法设计、近似算法性能分析及组合优化问题的计算复杂性理论分析。现主要从事组合优化中 的排序问题、装箱问题、设施选址问题及物流问题的优化设计与复杂性研究,相关研究发表在 在SIAM J. Comput. ,EJOR 及应用数学学报等国内外相关杂志上。


报告3 (9:50-10:30) :Saturation Numbers for Disjoint Stars

报告人:陆玫教授,清华大学数学科学系

报告摘要:A graph G is called an H-saturated if G does not contain H as a subgraph, but the addition of any edge between two nonadjacent vertices in G results in a copy of H in G.  The saturation number sat(n, H) is the minimum number of edges in G for all H-saturated graphs G of order n. For a graph F , let mF denote the disjoint union of m copies of F . In 2011, Faudree, Faudree and Schmitt proposed a problem that is to determine sat(n, mK1,k) for all m and k . In this talk, I will give a result on sat(n, mK1,k) when m ≥ 2, k ≥ 4 and n ≥ 3mk2 . This work is joint with Zequn Lv and Zhen He.

个人简介:陆玫,1993 年7 月在中国科学院数学与系统科学研究院获博士学位,现为清华大学 数学科学系教授,博士生导师,主要从事运筹学、图论与组合优化方面的研究。


报 告4  (10:30-11:10) :The scheduling problem with assignable or generalized due dates to minimize total weighted late work

报告人:原晋江教授,郑州大学数学与统计学院

报告摘要:Mosheiov et al.  (2021) introduced and studied the single-machine scheduling for minimizing the total weighted late work with assignable due dates (ADD-scheduling) and gen- eralized due dates (GDD-scheduling).  As a continuation of their research work, we revisit the following three problems: (i) the GDD-scheduling problem for minimizing the total weighted late work, (ii) the ADD-scheduling problem for minimizing the total weighted late work, and (iii) the ADD-scheduling problem for minimizing the total late work. Mosheiov et al. (2021) showed that the above three problems are NP-hard and posed their exact complexity (unary NP-hardness or pseudo-polynomial-time solvability) as open. In this paper, we address these open problems by showing that the first two problems are unary NP-hard and the third problem admits pseudo- polynomial-time algorithms. For the third problem, we also present a 2-approximation solution and a fully polynomial-time approximation scheme. Computational experiments show that our algorithms and solutions are efficient. When the jobs have identical processing times, we further present more efficient polynomial-time algorithms.

个人简介:原晋江现任郑州大学数学与统计学院教授、博士生导师、教授委员会主任、SCI 期刊《Journal of Scheduling》编委会成员。1995 年于四川大学应用数学专业获得理学博士学位。研究兴趣主要在排序、图论、组合最优化等领域。 曾发表SCI 期刊学术论文二百余篇,主 持国家基金项目8 项,并与团队成员一起攻克了排序问题的计算复杂性研究中的二十多个历史 遗留问题。



2    2022年6月16号上午 (周四) 报告

报告1(8:30-9:10) :Recursion formulas, concentration polytopes, and sharp affine isoperimetric inequalities for volume decomposition functionals

报告人:熊革教授,同济大学数学科学学院

报告摘要:New sharp affine isoperimetric inequalities for the volume decomposition functionals are established.  To attack these extremal problems, we find the recursion formulas of volume decomposition functionals, then introduce concentration polytope and characterize its geometric structure, especially its vertices and 1-dimensional faces. The concentration polytope intuitively reinterprets the discrete logarithmic Minkowski problem.

个人简介:熊革,同济大学教授,博士生导师。研究领域是凸体几何。熊革教授解决了凸体 几何中的几个公开问题。包括Lutwak-Yang-Zhang 关于锥体积泛函极值问题的2, 3 维情形: 由截面确定凸体的Baker-Larman  问题的2维情形 。他与学生最早提出、并解决了Lp 静电容 量的Minkowski  问题:完全解决了纽约大学G. Zhang 教授关于凸体的John 椭球与对偶惯性 椭球一致性的问题 。熊革教授在国际纯数学的重要期刊JDG, AIM, IUMJ, IMRN, CVPDE, JFA ,CAG, Israel Journal of Mathematics, Discrete and Computational Geometry 等上发表 论文30 余篇 。他的多个研究成果被写入凸体几何的经典教材《Geometric Tomography》和 《Convex Bodies: the Brunn-Minkowski theory》之中。

报告2(9:10-9:50) :Matrix-exact Covers of Minimum-Cost-Spanning-Tree Games 报告人:曹志刚教授,北京交通大学经济管理学院

报告摘要:The minimum-cost-spanning-tree (m.c.s.t.)  game is a classical cooperative game model that has been extensively studied. We consider the problem of decreasing the connection costs as much as possible in an m.c.s.t.  game such that its core does not change.  We define the desired m.c.s.t. game as the matrix-exact cover of the original m.c.s.t. game, and show its existence and uniqueness by providing an explicit formula.  Our results also imply that the set of all m.c.s.t.  games with the same core possesses a meet-semilattice structure:  if two m.c.s.t. games have the same core, and we construct a new m.c.s.t.  game by defining the cost of each edge as the minimum between the corresponding connection costs of the two games, then the new game has the same core too.  (joint work with Zhibin Tan and Zhengxin Zo.

个人简介:曹志刚,北京交通大学经济管理学院教授。2010年毕业于中科院数学与系统科学研 究院并留院任助理研究员。2017年9月加盟北京交通大学经济管理学院,任 "卓越百人计划" 教授。长期从事合作博弈、交通博弈、网络博弈和算法博弈等方面的研究,在包括Operations Research 、Mathematics of Operations Research 、Games and Economic Behavior 、Journal of Mathematical Economics 、Social Choice and Welfare 、International Journal of Game Theory和 《中国科学:数学》在内的期刊上发表多篇论文。相关成果曾获中国信息经济学理论贡献奖、 系统科学与系统工程青年科技奖、中国决策科学青年科技奖和关肇直青年研究奖等荣誉。先后 主持国家自然科学基金委的青年、面上和优青项目。兼任中国 "双法"研究会智能决策与博弈分会副理事长,中国运筹学会博弈论分会副理事长,中国双法学会青年工作委员会副秘书长、 网络科学分会副秘书长,中国信息经济学会常务理事和中国运筹学会理事等职务。

报告3(9:50-10:30) :The number of maximum dissociation sets in trees

报告人:史永堂教授,南开大学组合数学中心

报 告摘要:A subset of vertices is a maximum independent set if no two of the vertices are adjacent and the subset has maximum cardinality.  A subset of vertices is called a maximum dissociation set if it induces a subgraph with vertex degree at most  1,  and the subset has maximum cardinality.  In this talk, we will introduce the result on the maximum number of maximum dissociation sets in trees. Joint work with Jianhua Tu and Zhipeng Zhang.

个人简介:史永堂,南开大学教授,博士生导师。2004年获得西北大学学士学位,2009年获得 南开大学博士学位,主要研究方向为图论与组合优化,主持多项国家自然科学基金和天津市自 然科学基金。现担任天津市工业与应用数学学会秘书长,中国运筹学会理事、图论组合分会常 务理事,中国工业与应用数学学会图论组合及其应用专委会常务委员等。

报告4(10:30-11:10) :待通知

报告人:马杰教授,中国科学技术大学数学科学学院

报告摘要:待通知

个 人 简 介:马杰, 中国科学技术大学数学学院教授,2011年获美国佐治亚理工学院数学博 士,2007年获中国科学技术大学数学学士。入选海外高层次人才引进计划青年项目、国家基金 委优秀青年科学基金项目、国家基金委杰出青年科学基金项目,曾获中国工业与应用数学学会 应用数学青年科技奖、国际组合学及其应用协会Hall奖,2018年起担任美国工业与应用数学学 会离散数学杂志(SIDMA)编委。马杰的研究工作集中在组合数学的若干前沿领域,包括极值图 论、结构图论、组合概率方法以及它们在信息科学和计算机科学中的应用。




3    2022年6月17号上午 (周五) 报告

报告1 (8:30-9:10) :布雷斯悖论与自私路由

报告人:胡旭东研究员,中国科学院数学与系统科学研究院

报告摘要:德国数学家迪特里希 ·布雷斯(Dietrich Braess) 在1968 年发现:在个人独立选择 路径的情况下,为交通路网增加额外的通行能力,反而有可能导致整个路网的整体运行水平降 低:这一反直观的现象被称为布雷斯悖论。报告人将介绍如何用算法博弈论中自私路由(Selfish Routing) 的模型与方法分析布雷斯悖论,以及在对两个网络博弈问题的研究中取得的成果。

个人简介:胡旭东,研究员,博士生导师:现任中国运筹学会理事长。1985 年毕业于清华大 学,获应用数学专业学士学位,1989 年毕业于中国科学院应用数学研究所,获运筹与控制论专 业博士学位。 自1989 年始,一直在中科院从事运筹学的理论研究和教学工作,主要研究方向为 组合优化、网络博弈、近似算法。2012 年被评为第五届"全国优秀科技工作者"。

报告2 (9:10-9:50) :An improved approximation algorithm for maximizing a DR-submodular function over a convex set

报告人:徐大川教授,北京工业大学数学学院

报告摘要:Maximizing a DR-submodular function subject to a general convex set is an NP-hard problem arising from many applications in combinatorial optimization and machine learning. While it is highly desirable to design efficient  approximation  algorithms under this general setting where neither the objective function is monotonic nor the feasible set is down-closed, unfortunately, Vondrak (2013) shows that such a problem admits no constant approximation under the value oracle model.  Our main contribution is to present a  = 0.25-approximation Frank-Wolfe type of algorithm with a sub-exponential time-complexity under the value oracle model,  improving  a previous  approximation ratio of    ≈  0.1924 with the same order of time-complexity by Durr et al.  (2021).  In the process, we also introduce a few new ideas of independent interests, including the exponential integrator method to discretize the ordinary differential equation (ODE) in the continuous-time Frank-Wolfe algorithm, and the Lyapunov function approach to streamline the analysis of the approximation ratio and/or the convergence rate in both the continuous and discrete settings.  (Joint work with Donglei Du, Zhicheng Liu, Chenchen Wu, and Yang Zhou).

个人简介:徐大川,北京工业大学数学学院运筹学与控制论责任教授,数学/统计学博士生导  师。北京工业大学区块链研究中心副主任。2002 年于中国科学院数学与系统科学研究院获得博  士学位。研究兴趣包括:组合优化、近似算法、机器学习等。中国运筹学会数学规划分会理事  长,中国运筹学会常务理事,北京运筹学会副理事长。担任AMC 、APJOR 、JORSC 、运筹与  管理等期刊编委。在科学出版社出版学术专著《设施选址问题的近似算法》,在Mathematical   Programming ,Operations Research ,INFORMS Journal on Computing ,Omega ,Algorithmica, Journal of Global Optimization ,Theoretical Computer Science ,Information Process Letters,   Journal of Combinatorial Optimization ,Operations Research Letters等期刊和AAAI, ICDCS,   COCOON等会议发表学术论文100 余篇。