论文标题
线性时间参数化算法，本地资源有限
Linear-Time Parameterized Algorithms with Limited Local Resources
论文作者
论文摘要
我们提出了一个新的（理论）计算模型，用于研究有限的计算资源的大规模数据处理。我们的模型根据数据大小n来衡量读取非常大的数据集的复杂性，并根据参数k来分析计算成本，该参数k表征了有限的本地计算资源提供的计算能力。我们开发了新的算法技术，这些技术实施算法来解决所提出的模型上众所周知的计算问题。特别是，我们提出了一种算法，该算法在时间O（n + k^{2.5}）的一般未加权图中找到k匹配和一种算法，该算法在时间O（n + k^3 log K）中构建一般加权图中最大加权k匹配的算法。两种算法的空间复杂性都受O（k^2）的界定。
We propose a new (theoretical) computational model for the study of massive data processing with limited computational resources. Our model measures the complexity of reading the very large data sets in terms of the data size N and analyzes the computational cost in terms of a parameter k that characterizes the computational power provided by limited local computing resources. We develop new algorithmic techniques that implement algorithms for solving well-known computational problems on the proposed model. In particular, we present an algorithm that finds a k-matching in a general unweighted graph in time O(N + k^{2.5}) and an algorithm that constructs a maximum weighted k-matching in a general weighted graph in time O(N + k^3 log k). Both algorithms have their space complexity bounded by O(k^2).
