2017组合数学研讨会

发布时间:2017年11月23日 作者:唐颖   消息来源:业务办    阅读次数:[]

报告题目: Perfect r-code in graphs

报告人:陆玫 清华大学教授

报告时间:2017年11月26日上午9点至9:45点

报告地点:数理楼六楼数学系教研室

摘要: A perfect r-code in a graph is a subset of the graph's

vertices with the property that each vertex in the graph is within

distance r of exactly one vertex in the subset. In this talk, some results of perfect r-code in products of Graphs were given.

陆玫,1993年7月在中国科学院数学与系统科学研究院获博士学位,现为清华大学数学科学系教授,博士生导师,主要从事运筹学、图论与组合优化方面的研究,发表SCI检索学术论文50余篇。现任清华大学数学科学系计算数学与运筹学研究所所长。

报告题目: A Tractable Network Game of Atomic Dynamic Flows

报告人:陈旭瑾 中科院数学与系统科学院研究员

报告时间:2017年11月26日上午10点至10:45点

报告地点:数理楼六楼数学系教研室

摘要:Selfish routing, a fundamental problem with diverse real-world applications, is dynamic in nature. However, the combination of selfishness and dynamic feature poses challenges for integrating accuracy and tractability into its modeling. Based on a discrete version of deterministic queuing, we propose a network game to model the selfish routing generated by dynamic traffic of atomic agents who travel from possibly different origins to a common destination, where the traffic is regulated with given priorities on edges (e.g., road segments). We demonstrate the tractability of our model, which helps to regulate selfish behaviors for individual earliest arrival at the destination towards system stability and efficiency.

Two forms of the game are considered. In the norm-form game Π, all agents are non-adaptive, selecting and fixing their own origin-destination paths simultaneously at the very beginning. In the extensive-form game Λ, each agent is adaptive, making an online decision at each nonterminal vertex (e.g., road crossing) he reaches as to which is the next edge to take. We show that both forms of the game admit computable equilibria, i.e., Nash equilibrium (NE) for Π and subgame perfect equilibrium (SPE) for Λ. We prove that the NE set of Π is properly “contained” by the SPE set of Λ, which indicates more flexibility achieved by adaptive agents. We characterize all NEs of Π with a feature of iterative group domination, which particularly implies all the equilibria are weakly Pareto optimal and possess global first-in-first-out property.

Our work shows that edge priorities play a crucial role for the tractabilities of the network game model. On the other hand, our model is rich enough as well to allow for some interesting phenomena, including agents’ vicious behaviors and a new Braess-like paradox. (Joint work with Zhigang Cao, Bo Chen, Changjun Wang)

陈旭瑾 中科院数学与系统科学院研究员 2004年毕业于香港大学,获数学哲学博士学位,主要从事 组合优化 近似算法设计 算法博弈论等方向,发表SCI论文60余篇,2010年获中国运筹学会青年科技奖一等奖。2012年获国家自然科学基金委优秀青年科学基金项目。工作经历: 2009年3月-目前,中国科学院数学与系统科学研究院,基地副研究员 2006年9月-2009年2月,中国科学院数学与系统科学研究院,基地助理研究员 2004年9月-2006年8月,中科院应用数学所, 博士后(合作导师:胡晓东研究员)学术访问: 2010年10月- 2010年11月,德国Max-Planck Institute for Informatic,Visiting Associate Professor 2007年9月-2008年5月,美国Louisiana State University,Visiting Assistant Professor 2007年3月-2007年6月,中国Hong Kong University, Research Visitor 2006年3月- 2006年8月,英国Warwick University, Visiting Fellow

报告题目:Chemical Indices of Graphs with Degree Sequences

报告人:张晓东 上海交通大学教授

报告时间:2017年11月26日上午11点至11:45点

报告地点:数理楼六楼数学系教研室

摘要: The chemical indices, such as the Wiener index, ABC index,

Harry index, Zagreb Index etc, of a graph have received a lot of attention.

In this talk, we introduce some progress and new results on these chemical

indices of graphs with given degree sequences. In addition, some problems are

concluded.

张晓东,上海交通大学数学系教授,博士生导师,理学博士,世界华人数学家大会邀请的报告者。主要从事图论和组合学及其应用的研究。曾经在以色列理工学院、智利大学从事博士后研究工作,在美国加州大学圣地亚哥分校、韩国庆北大学和全北大学做高级访问学者。先后主持多项国家自然科学基金项目和参加973国家基础科研基金资助项目、863国家高科技发展基金资助项目、国家自然科学基金重点项目和上海市科委的重大研究项目等。获得省科技进步奖两项。已经在国际上SCI期刊发表100多篇论文,其中部分的研究结果已经被写入国外专著。目前担任两个国际期刊杂志的编委。



打印】【收藏】 【关闭