查看原文
其他

IJTCS 2021 | 会议接收论文(部分报告)介绍


编者按


第二届国际理论计算机联合大会(International Joint Conference on Theoretical Computer Science,IJTCS)将于2021年8月16日-20日在线上线下交互举行,由北京大学中国工业与应用数学学会(CSIAM)、中国计算机学会(CCF)、国际计算机学会中国委员会(ACM China Council)联合主办,北京大学前沿计算研究中心承办,图灵奖获得者、中科院外籍院士、北京大学访问讲席教授John Hopcroft教授任大会主席。


本期带来“CSIAM 区块链”“算法与复杂性”分论坛接收论文(部分报告)的精彩介绍。

“CSIAM区块链”接收论文报告议程

时间:2021年8月17日

时间

讲者

报告题目

11:00-

11:25 

Xu Wang

Framework and algorithms for identifying honest blocks in blockchain

 

时间:2021年8月19日

时间

讲者

报告题目

19:00-

19:25 

Yuncheng

Qiao

Block-CES: Multi-institution collaborative credit evaluation system based on blockchain

19:30-

19:55 

Zhengtang

Fu

An intelligent electric vehicle charging system for new energy companies based on consortium blockchain


“CSIAM 区块链”接收论文报告介绍


 

Framework and algorithms for identifying honest blocks in blockchain

Xu Wang, Tsinghua University

Abstract

Blockchain technology gains more and more attention in the past decades and has been applied in many areas. The main bottleneck for the development and application of blockchain is its limited scalability. Blockchain with directed acyclic graph structure (BlockDAG) is proposed in order to alleviate the scalability problem. One of the key technical problems in BlockDAG is the identification of honest blocks which are very important for establishing a stable and invulnerable total order of all the blocks. The stability and security of BlockDAG largely depends on the precision of honest block identification. This paper presents a novel universal framework based on graph theory, called MaxCord, for identifying the honest blocks in BlockDAG. By introducing the concept of discord, the honest block identification is modelled as a generalized maximum independent set problem. Several algorithms are developed, including exact, greedy and iterative filtering algorithms. The extensive comparisons between proposed algorithms and the existing method were conducted on the simulated BlockDAG data to show that the proposed iterative filtering algorithm identifies the honest blocks both efficiently and effectively. The proposed MaxCord framework and algorithms can set the solid foundation for the BlockDAG technology.


Biography

Wang Xu received his Ph.D. degree in Operations Research and Cybernetics from Academy of Mathematics and Systems Science, Chinese Academy of Sciences, in 2020. Now he is a postdoctoral fellow in Department of Industrial Engineering, Tsinghua University. His research focuses on blockchain technology and operations research, and the optimization modeling in traffic.


 

Block-CES: Multi-institution collaborative credit evaluation system based on blockchain

Yuncheng Qiao, Hunan University

Abstract

Data sharing among different institutions can enhance the integrity of information, so as to evaluate the credit level of financing enterprises more accurately, but it also faces the problems of privacy leakage and data fraud. This paper proposes a credit evaluation system with secure sharing and multiparty collaborative computing based on blockchain. The system ensures the authenticity of data by the characteristics of irrevocability and traceability of blockchain. It simultaneously enables institutions to complete the construction of credit evaluation model without exposing their own data, and solves the privacy protection problem of collaborative computing among multiple institutions. The system consists of four modules: distributed ledger, access control, security aggregation and model storage. The distributed ledger module based on hyperledger fabric ensures the trusted storage of data. The access control module avoids unauthorized data access. The security aggregation module realizes the privacy of data transmission and collaborative computing process by elementary matrix transformation and 1-out-of-N oblivious transmission protocol, which makes it more consistent with the minimum principle of data transmission in GDPR and other regulations. Finally, a calculation case is given to show the detailed process of each participant building credit evaluation model by using security aggregation protocol. And the consistency of model parameters before and after privacy protection is verified.


Biography

Yuncheng Qiao is currently a Ph.D. candidate in management science and engineering, business school, Hunan University. His research interest lies in blockchian, privacy computation, credit evaluation, etc. He has applied for 2 patents, and published many papers in international journals and conferences such as ADV DIFFER EQU-NY, ACTA MATH APPL SIN-E, etc.


 

An intelligent electric vehicle charging system for new energy companies based on consortium blockchain

Zhengtang Fu, Beijing Institute of Technology

Abstract

With the concerns of environment protection, electric vehicle (EV) is regarded as a promising transportation tool for green cities project. Since the amount of EVs is rising shapely, the EV charging demands is also rapidly generated. However, seeking suitable charging facilities is not easy for EV users, new energy companies run charging stations separately for self-interests, and charging pile information is not transparent for drivers. This dilemma is not solved until the merging of blockchain technology. In this paper, a novel EV charging system is proposed for the cooperation of new energy companies and providing convenient charging services for users. In this system, charging information is managed and recorded by the company alliance based on consortium blockchain, which is tamper-resistant and multi-centralized. Meanwhile, a new smart contract is designed to balance the allocation of company' charging users, so that the profits of different new energy companies could be fairer. To equilibrate the interest of companies and EV users, a Bio-Objective Mixed-Integer Programming model (BOMILP) is proposed as the mathematical logic of smart contracts. Furthermore, we proposed a new algorithm named Limited Neighborhood Search with Memory (LNSM) to support the implementation of smart contracts, which could make the smart contract running faster and has a better performance. At last, the proposed EV charging system and the smart contract are validated through a real case study with the EV charging data in Beijing, China.


Biography

Zhengtang Fu is currently pursuing the Ph.D. degree with the Beijing Institute of Technology, Beijing, China. He received the master's degree from Shanghai Maritime University, Shanghai, China, in 2016. He owns plenty of working experience, including a consulting company, an European integration company, and a local intelligent manufacturing company. The latest working experience is Shanghai Inlaylink Internet of Things Technology Corporation as the Project Manager. He has published several papers related to simulation, algorithm, and data analysis. His research interests include the application of blockchain technology, the Internet of Things (IoT), and complex system.

“算法与复杂性”接收论文报告议程

时间:2021年8月18日

时间

讲者

报告题目

21:00-

21:25 

Manolis

Vasilakis

Faster Algorithms for k-SubsetSum and Variations

21:30-

21:55 

Mingyang

Gong

Improved approximation algorithms for multiprocessor scheduling with testing

22:00-

22:25 

Yong

Chen

Approximation algorithms for the directed path partition problems

22:30-

23:00 

Liangde

Tao

Hardness and Algorithms for Electoral Manipulation under Media Influence


“算法与复杂性”接收论文报告介绍


 

Faster Algorithms for k-SubsetSum and Variations

Manolis Vasilakis, National Technical University of Athens

Abstract

We present new, faster pseudopolynomial time algorithms for the  -SubsetSum problem, defined as follows: given a set  of  positive integers and  targets  determine whether there exist  disjoint subsets  , such that  , for  .


Assuming  is the maximum among the given targets, a standard dynamic programming approach based on Bellman's algorithm can solve the problem in  time.


We build upon recent advances on SubsetSum due to Koiliaris and Xu [Koil19] and Bringmann [Brin17] in order to provide faster algorithms for  -SubsetSum.


We devise two algorithms: a deterministic one of time complexity  and a randomised one of  complexity.


We further demonstrate how these algorithms can be used in order to cope with variations of  -SubsetSum, namely SubsetSumRatio,   -SubsetSumRatio and MultipleSubsetSum.


Biography

Manolis Vasilakis recently received the diploma in Electrical and Computer Engineering from the National Technical University of Athens with specialization in Computer Science. His interests lay in the field of theoretical computer science, and more specifically in approximation algorithms, subset sum/knapsack problems and fine grained complexity.


 

Improved approximation algorithms for multiprocessor scheduling with testing

Mingyang Gong, University of Alberta

Abstract

Multiprocessor scheduling, also called scheduling on parallel identical machines to minimize the makespan, is a classic optimization problem that has received numerous studies.


Scheduling with testing is an online variant where the processing time of a job is revealed by an extra test operation, or otherwise the job has to be executed for a given upper bound on the processing time. Albers and Eckl recently studied the multiprocessor scheduling with testing; among others, for the non-preemptive setting they presented an approximation algorithm with competitive ratio approaching 3:1016 when the number of machines tends to infinity and an improved approximation algorithm with competitive ratio approaching 3 when all test operations take a time unit. We propose to first sort the jobs into the non-increasing order of the ratio between the upper bound and the testing time, then partition the jobs into three groups and process them group by group according to the sorted job order. We show that our algorithm achieves improved competitive ratios, which approach 2:9513 when the number of machines tends to infinity in the general case; when all test operations take a time unit, our algorithm achieves even better competitive ratios approaching 2:8081.


Biography

Mingyang Gong is pursuing the Ph.D. in Department of Computer Science at University of Alberta. He received his Bachelor of Natural Sciences in Mathematics and Applied Mathematics in 2018 and Master in School of Mathematical Sciences in 2021 at Zhejiang University.


 

Approximation algorithms for the directed path partition problems

Yong Chen, Hangzhou Dianzi University

Abstract

Given a digraph G=(V,E), the k-path partition problem is to find a minimum collection of vertex-disjoint directed paths each of order at most k to cover all the vertices of V. The problem has various applications in facility location, network monitoring, transportation and others. Its special case on undirected graphs has received much attention recently, but the general version is seemingly untouched in the literature. We present the first k/2-approximation algorithm, for any k>=3, based on a novel concept of augmenting path to minimize the number of singletons in the partition. When k>=7, we present an improved (k+2)/3-approximation algorithm based on the maximum path-cycle cover followed by a careful 2-cycle elimination process. When k=3, we define the second novel kind of augmenting paths to reduce the number of 2-paths and propose an improved 13/9-approximation algorithm.


Biography

Yong Chen is currently an associate professor at the department of mathematics at Hangzhou Dianzi University. He received his Ph.D. in 2011 from the Department of Mathematics at Zhejiang University.  He received his Bachelor's degree in 2005 from the Department of Mathematics at Hangzhou Dianzi University.  Professor Chen's main research is the design of approximation algorithm for NP-hard combinatorial optimization problem under different models.


 

Hardness and Algorithms for Electoral Manipulation under Media Influence

Liangde Tao, Zhejiang University

Abstract

In this paper, we study a generalization of the classic bribery problem known as electoral manipulation under media influence (EMMI). This model is motivated by modern political campaigns where candidates try to convince voters through advertising in media (TV, newspaper, Internet). When compared with the classical bribery problem, the attacker in this setting cannot directly change opinions of individual voters, but instead can execute influences via a set of manipulation strategies (e.g., advertising on a TV channel). Different manipulation strategies incur different costs and influence different subsets of voters. Once receiving a significant amount of influence, a voter will change opinion. To characterize the opinion change of each voter, we adopt the well-accepted threshold model. We prove the NP-hardness of the EMMI problem and give a dynamic programming algorithm that runs in polynomial time for a restricted case of the EMMI problem.


Biography

Liangde Tao is a PhD student major in Computer Science at Zhejiang University. Previously, he obtained his B.E. from Zhejiang University (2012-2016). His research interests are broadly in optimization and approximation algorithms.

关于IJTCS

回顾 → 对话邓小铁:在首届IJTCS中,我看到了中国计算理论的成长

日程 → 推   荐:大会特邀报告

日程 → 分论坛:算法博弈论

日程 → 分论坛:区块链技术

日程 → 分论坛:多智能体强化学习

日程 → 分论坛:机器学习理论

日程 → 分论坛:量子计算

日程 → 分论坛:人工智能与形式化方法

日程 → 分论坛:算法与复杂性

日程 → 分论坛:计算经济学

日程 → 分论坛:有意识的图灵机

日程  特   色:本科生论坛

日程 → 特   色:女性论坛

日程 → 特   色:青年博士论坛

日程 特   色:CFCS理论计算青年教师论坛

IJTCS注册信息

大会现已正式面向公众开放注册


观看线上报告:免费

通过在线观看直播的方式参与大会,可通过直播平台提问。


线上会议注册

(普通)$100 /¥700

(学生)$50 /¥350*

获得所有Zoom会议参会链接,作为参会人在线参加全部会议,直接在线提问讨论并参与特设互动环节


线下会议注册

(普通)$200 / ¥1400

(学生)$100 / ¥700*

作为参会人在线下(北京大学)参加会议,与知名学者们面对面交流;同时享受线上注册的所有权益。

*因防疫要求,仅开放10个校外线下参会名额。


点击 ↓↓↓二维码↓↓↓ 跳转注册页面

*学生注册:网站上注册后需将学生证含有个人信息和学校信息的页拍照发送至IJTCS@pku.edu.cn,邮件主题格式为"Student Registration+姓名+线上/线下"。


大会主席 

 

John Hopcroft

图灵奖获得者

中国科学院外籍院士

北京大学访问讲席教授


大会联合主席 

 

邓小铁

北京大学讲席教授

欧洲科学院外籍院士

ACM/IEEE Fellow


顾问委员会主席 

   

高  文

中国工程院院士

北京大学教授

梅  宏

中国科学院院士

CCF理事长

张平文

中国科学院院士

CSIAM理事长

北京大学教授


程序委员会主席 

   

孙晓明

中科院计算所

研究员

邓小铁

北京大学

讲席教授

李闽溟

香港城市大学

副教授


  

陆品燕

上海财经大学

教授

李  建

清华大学

副教授


组织单位 


合作媒体


大会赞助


联系人

大会赞助、合作等事宜

请联系

IJTCS@pku.edu.cn

010-62761029

大会网站

https://econcs.pku.edu.cn/ijtcs2021/index.htm

↑↑扫码直达大会官网↑↑


文字 | 霍子璇



—   版权声明  —

本微信公众号所有内容,由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料,版权属北京大学前沿计算研究中心微信所有;从公开渠道收集、整理及授权转载的文字、图片和音视频资料,版权属原作者。本公众号内容原作者如不愿意在本号刊登内容,请及时通知本号,予以删除。


“阅读原文”转大会注册页面

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存