On optimal streaming kernelization algorithms  

作　　者：Hao FENG Wei YANG Jianer CHEN 

机构地区：[1]School of Computer Science,Guangzhou University,Guangzhou 510006,China [2]Department of Computer Science and Engineering,Texas A&M University,College Station,TX 77843,USA

出　　处：《Science China(Information Sciences)》2024年第8期333-334,共2页中国科学（信息科学）（英文版）

摘　　要：The streaming model has been a popular model in big data computation.Streaming kernelization algorithms can be regarded as data compression processes on streaming data.In this study,we give a general method for developing computational lower bounds for streaming kernelization algorithms that is applicable to a large class of computational problems.As an example,we use the method to prove computational lower bounds for the well-known problem d-HITTINGSET.This result shows that a streaming kernelization algoroithm we recently developed for the famous NP-hard problem VERTEx-CovER is optimal in all complexity measures,including space,update-time,and kernel size.

关 键 词：COMPUTATION PROBLEMS KERNEL 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]