一、会议简介

组合优化与算法理论是理论计算机科学的主要研究领域之一，是软件学科的基础研究内容，以及计算机科学和数学的交叉研究内容。本次会议邀请了国内组合优化和算法领域的知名学者，围绕计算经济学、参数算法、数论、机器学习、设施选址、次模优化等专题，就最新优秀研究成果做学术报告，并与参会同行作深入的研讨，提高学术研究水平，促进学术发展与合作。本系列会议第1届和第2届分别于2019年和2021年举办。

二、 会议基本情况

1. 承办单位（邀请人）：山东大学软件学院，张鹏教授。

2. 会议时间：2022年7月22日 8:30-17:30

3. 会议方式：腾讯会议，会议号：314 976 179

三、 会议日程

四、 专家报告

1.报告专家：高晓沨

报告题目： 众包与群智：共享经济新模式

摘要：随着移动互联网和智能终端的不断普及，人与万物通过网络紧密联系在一起，信息的交互正变得越来越频繁。与此同时，基于大数据计算与分析的城市管理愈加精准，共享经济的蓬勃发展令社会生活变得愈发便利。大众点评让娱乐生活避免“踩雷”，“出行随手拍”让旅途更加通畅，共享单车解决了出行“最后一公里”的问题……众包（Crowdsourcing），作为一种利用群体合作共同完成任务的工作方式，让曾经难以实现的海量工作被大众解决，使生活更加美好。

众包任务的复杂度不高，但通常是一些人比机器更为擅长的工作；众包工作者也无须特别高的专业技能，从而可以得到大量候选者。例如，外卖配送通过大量配送员，将海量餐厅的美食送到民众家门口；网约车司机利用闲置的私家车，赚取外快的同时为社会提供更多运力。让众包如此井井有条，需要合理的匹配策略与调度算法，工作者的数量、平台和工作者的收益与代价等问题都需要仔细考量。其中涉及到的任务分配、路径规划和位置覆盖问题，大多可以建模为经典的组合优化问题，如旅行商问题（TSP）等，采用机器学习的方法来求解此类问题正成为当下一个热门的研究点。

本报告将对众包的相关概念、特点和应用进行概述，并对近几年学术界对众包任务分配与调度的成果进行综述，最后介绍主讲人团队在相关领域十余年的工作历程，以启发听众理解研究领域的长线脉络、主题迁移和技术变革。

简介：高晓沨，上海交通大学计算机科学与工程系教授、博导。本科毕业于南开大学数学系，硕士毕业于清华大学数学系，博士毕业于美国德克萨斯大学达拉斯分校计算机系，师从著名运筹学家堵丁柱教授。研究方向为数据工程、网络优化等，发表中国计算机学会推荐期刊会议（CCF-A/B区）论文130余篇，如IEEE/ACM Trans系列期刊TON、TPDS、TMC、TKDE、TC、JSAC，以及国际会议SIGKDD、INFOCOM、ICDE、WWW、NeurIPS、IJCAI等。

任中国计算机学会分布式计算与系统专委会常务委员、数据库专委会委员、大数据专家专委会委员；中国运筹学会数学规划分会青年理事；IEEE、ACM、CCF高级会员等。曾获教育部青年长江学者、上海市科委“浦江人才”、上海市教委“晨光计划”、“宝钢优秀教师奖”等资助和荣誉。曾八次荣获国际学术会议最优论文奖，包括DASFAA2017（CCF-B）、ICPADS2016（CCF-C）等。有丰富的校企合作经验，与腾讯、华为、阿里、百度、字节跳动等互联网企业及中远海运集团、长虹集团等实体业开展合作，曾获CCF-腾讯犀牛鸟基金卓越奖、CCF-华为创新研究计划结题第一名（均为年度最高奖）等荣誉。

2.报告专家：李文军

报告题目： 深层局部搜索在核心化算法中的运用

摘要：随着经济的迅速发展，各行各业涌现出越来越多的计算难解问题。作为计算难解问题的一种预处理手段，参数计算中的核心化算法能在多项式时间内有效降低问题实例的规模，因此在许多领域有着广泛的应用。核心化技术作为核心化算法性能优劣的关键因素，一直是参数计算领域的一个研究热点。本报告将探讨深层局部搜索在核心化算法中的运用，对基于深层局部搜索的三个FPT问题的核心化进行举例，并提出了两个开放性问题供大家交流。

简介： 李文军，博士，副教授，长沙理工大学计算机与通信工程学院副院长，湖南省青年骨干教师培养对象、CAAI智慧医疗专委会委员、CCF理论计算机科学专业委员会委员、湖南省人工智能学会理事、湖南省计算机学会理事，主要研究领域为参数算法优化。主持在研国家自然科学基金面上项目1项，主持完成国家自然科学青年基金项目1项、湖南省科技厅青年项目1项、教育厅一般项目1项；在Information and Computation、Algorithmica、Theoretical Computer Science、ESA等CCF推荐的CCF A、B类国际知名期刊和会议上发表论文20余篇。

3. 报告专家：许超

报告题目：Almost optimum ℓ-covering of Z_n

摘要：A subset B of ring Z_n is called a ℓ-covering set if {ab (mod n) | 0 £ a £ ℓ, b Î B} = Z_n. We show there exists a ℓ-covering set of Z_n of size O((n / ℓ) log n) for all n and ℓ, and how to construct such set. The proof uses a refined bound for relative totient function obtained through sieve theory, and existence of a large divisor with linear divisor sum. We also show examples where any ℓ-covering set must have size W((n / ℓ) (log n / loglog n)).

This is joint work with Ke Shi.

简介：Chao Xu is currently an Assistant Professor at Algorithms and Logic Group in UESTC. He obtained a Ph.D. of Computer Science at UIUC in May 2018. He works in the area of combinatorial optimization, algorithms and computational geometry.

4. 报告专家：许宜诚

报告题目：The fair k-supplier

摘要：Inspired by recent research trends of fair clustering, we introduce the fair k-supplier problem in this paper, from both facility and client perspectives. In the facility-fair k-supplier problem, the facility set is partitioned into m groups, and the goal is to find a minimum k-supplier solution such that the amount of open facilities in each group does not exceed a corresponding upper bound. In the client-fair k-supplier, the client set is partitioned into w groups, and the goal is to find a minimum k-supplier solution such that the amount of served clients in each group is not less than a corresponding lower bound. Both problems generalize the classic k-supplier and are thus NP-hard to approximate within a factor less than 3. We propose a 5-approximation for facility-fair k-supplier and a pseudo 5-approximation for client-fair k-supplier respectively, where the pseudo approximation algorithm violates the cardinality constraint by at most w.

简介：中国科学院深圳先进技术研究院副研究员，中国科学院大学硕士生导师。2018年毕业于北京工业大学，获优秀博士学位论文，随后加入先进院先后任博士后、助理研究员和副研究员。目前开设一门博士生课程《高级算法》，研究兴趣主要是组合优化和计算经济问题的近似算法。

5.报告专家：韩璐

报告题目：带下界约束的k-中位问题的近似算法研究

摘要：经典的k-中位问题在计算机科学和运筹学领域中均有着广泛的应用。本报告围绕此问题带下界约束的推广模型：即，带下界约束的k-中位问题。在带下界约束的k-中位问题中，给定设施集合，顾客集合、正整数k，以及下界限制L。若设施被开设，要求连接到它上面的顾客个数至少是L个。将顾客连接到设施上会产生连接费用。假设连接费用是非负的，对称的，且满足三角不等式。目标是开设至多k个设施，将每个顾客都连到开设的设施上，使得每个开设的设施上至少连接L个顾客，并且连接费用之和最小。本报告将介绍与带下界约束的k-中位问题相关的研究背景，首先给出问题的双标准近似算法，此算法的解能够满足基数约束（即，开设不超过k个设施），并近似满足下界约束（即，每个开设的设施上至少连接L个顾客）。其次，给出带下界约束的k-中位问题的两个常数近似算法，近似比分别是610和387, 主要基于归约与问题的结构提出。最后，研究在每个设施给定的下界限制不同时的带下界约束的k-中位问题：即，广义的带下界约束的k-中位问题。在此问题中，每个设施i给定不同的下界限制L_i。若设施i被开设，要求连接到它上面的顾客个数至少是L_i个。关于广义的带下界约束的k-中位问题，可给出此问题的常数近似算法，近似比是11021, 主要采用的还是基于归约的方法。

简介：韩璐，北京邮电大学特聘副研究员。研究方向为组合优化、近似算法。主要研究课题涉及到聚类问题，以及斯坦纳树问题。现主持国家自然科学基金青年基金一项，发表论文十余篇。

6.报告专家：杨瑞琪

报告题目：Multi-Pass Streaming Algorithms for Regularized Submodular Maximization

摘要：In this talk, we study the problem of maximizing a k-Cardinality Constrained Regularized Submodular Maximization (k-CCRSM) problem. In the model, the regularized objective function denoted by f() - c(), is the difference between a non-negative submodular function f and a non-negative modular function c. It has been concluded that no multiplicative factor approximation is possible and the most previous works pay attention to find slightly weaker approximations for such problems. In this work, we consider the k-CCRSM under a streaming fashion. Assume there exists a weaker r-approximation algorithm a prior for the discussed regularized problems, we present two boosting multi-pass streaming algorithms for the k-CCRSM with the submodular term are monotonic and non-monotonic in respectively. Specially, given some accuracy parameter e Î (0,1), we give a multi-pass stream algorithm for the monotone setting, in which it makes at most O(log(1/(er))/e) passes, needs O(n log(1/(er))/e) queries, consumes O(k) memory, and produces a solution S satisfying f(S) - e^{-(1-e)}c(S) ³ (1-e^{-1} - O(e)) (f(O) - c(O))，where O denotes the optimal solution of the stated problem. We further obtain a multi-pass stream algorithm for the k-CCRSM with the submodular term is non-monotonic. The algorithm makes at most O(log((1-e)^2 / (2e-e^2)) / e) passes, needs O(n log((1-e)^2 / (2e-e^2)) / e) queries, consumes O(k) memory, and produces a solution S obeying f(S) - c(S) ³ (1-e)/(2-e){min{1/2-e, 2(1-e)r}f(O) - 2(1-e)c(O)} for some e Î (0, 1/2).

简介：杨瑞琪，2022年7月进入北京工业大学理学部工作，聘为讲师。2020年6月博士毕业于北京工业大学，2020年6月-2022年6月，中国科学院大学博士后、特别研究助理。现任中国运筹学会宣传委员会副秘书长。主要研究兴趣包括：组合优化、近似算法、次模优化。在Science China: Information Sciences、Theoretical Computer Science、Discrete Applied Mathematics、Journal of Combinatorial Optimization等发表论文10余篇，主持国家自然科学青年基金、博士后面上基金等项目。