IJTCS | 分论坛日程：算法与复杂性
编者按
首届国际理论计算机联合大会（International Joint Conference on Theoretical Computer Science，IJTCS）将于2020年8月17日-21日在线上举行，由北京大学与中国工业与应用数学学会（CSIAM）、中国计算机学会（CCF）、国际计算机学会中国委员会（ACM China Council）联合主办，北京大学前沿计算研究中心承办。
本次大会的主题为“理论计算机科学领域的最新进展与焦点问题”。大会共设7个分论坛，分别对算法博弈论、区块链技术、多智能体强化学习、机器学习理论、量子计算、机器学习与形式化方法和算法与复杂性等领域进行深入探讨。同时，大会特别开设了青年博士论坛、女性学者论坛与本科生科研论坛，荟集海内外知名专家学者，聚焦理论计算机前沿问题。有关信息将持续更新，敬请关注！
本期带来“算法与复杂性”分论坛精彩介绍。
“算法与复杂性”介绍
算法与复杂性是理论计算机领域的基石，主要分为两个主要研究领域，其一是复杂性研究，针对的是研究各个复杂度类之间的关系，其终极目标是证明P是否等于NP。另一个是针对各种计算模型的算法设计及针对算法复杂性的分析，包括自动机理论，近似算法，在线算法，随机算法，图算法，流算法，分布式算法等等。在实际应用中产生的大多数问题都可以通过建模转变为一个理论问题进行算法和复杂性的研究，而得到的有理论保障的结果对实际问题有很大的指导意义。
在国内该领域的发展正在加速，越来越多的学者在该领域从事前沿的工作，并且时有突破性的结果出现。FAW（Frontiers of Algorithms Workshop）为立足于国内的专注与算法与复杂性的国际会议，本次会议旨在初步建立算法与复杂性分论坛与FAW的联系，并于之后进一步加强联系。
“算法与复杂性”分论坛主席
李闽溟
香港城市大学
“算法与复杂性”分论坛议程
时间：2020年8月17日
“算法与复杂性”分论坛报告简介
李闽溟
Defending with Shared Resources on a Network
Abstract
In this talk we consider a defending problem on a network. In the model, the defender holds a total defending resource of R, which can be distributed to the nodes of the network. The defending resource allocated to a node can be shared by its neighbors. There is a weight associated with every edge that represents the efficiency defending resources are shared between neighboring nodes. We consider the setting when each attack can affect not only the target node, but its neighbors as well. Assuming that nodes in the network have different treasures to defend and different defending requirements, the defender aims at allocating the defending resource to the nodes to minimize the loss due to attack. We give polynomial time exact algorithms for two important special cases of the network defending problem. For the case when an attack can only affect the target node, we present an LP-based exact algorithm. For the case when defending resources cannot be shared, we present a max-flow-based exact algorithm. We show that the general problem is NP-hard, and we give a 2-approximation algorithm based on LP-rounding. Moreover, by giving a matching lower bound of 2 on the integrality gap on the LP relaxation, we show that our rounding is tight.
关于IJTCS
简介 → 国际理论计算机联合大会重磅登场
推荐 → 大会特邀报告（一）
推荐 → 大会特邀报告（二）
日程 → 分论坛：算法博弈论
日程 → 分论坛：区块链技术
日程 → 分论坛：多智能体强化学习
日程 → 分论坛：机器学习理论
日程 → 分论坛：量子计算
日程 → 分论坛：机器学习与形式化方法
IJTCS注册信息
本次大会已经正式面向公众开放注册！每位参与者可以选择免费注册以观看线上报告，或是支付一定费用以进一步和讲者就报告内容进行交流，深度参与大会的更多环节。
观看线上报告：免费
完全注册：
（普通）$100 /￥700
（学生）$50 /￥350*
作为参会人参加全部会议，直接在线提问讨论并参与特设互动环节
注册截止：2020年8月15日23:59
点击 ↓↓↓二维码↓↓↓ 跳转注册页面：
*学生注册：网站上注册后需将学生证含有个人信息和学校信息的页拍照发送至IJTCS@pku.edu.cn，邮件主题格式为＂Student Registration + 姓名＂。
大会主席
John Hopcroft
中国科学院外籍院士、北京大学访问讲席教授
林惠民
中国科学院院士、中国科学院软件研究所专家
大会联合主席
邓小铁
北京大学教授
顾问委员会主席
高 文
中国工程院院士、北京大学教授
梅 宏
中国科学院院士、CCF理事长
张平文
中国科学院院士、CSIAM理事长、北京大学教授
组织单位
媒体合作
欢迎注册
大会网站：
https://econcs.pku.edu.cn/ijtcs2020/IJTCS2020.html
注册链接：
https://econcs.pku.edu.cn/ijtcs2020/Registration.htm
联系人
大会赞助、合作等信息，请联系：IJTCS@pku.edu.cn
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。
点“阅读原文”转大会注册页面