Kernelization for Big Data

大数据的内核化

• 批准号: 247801001
• 负责人: Professor Dr. Matthias Mnich
• 金额: --
• 依托单位: Institut für Algorithmen und Komplexität
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2014
• 资助国家: 德国
• 起止时间: 2013-12-31 至 2021-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/247801001?language=en
• 关键词: Kernelization; Big; Data

The main research goal of this project is the quest for a rigorous mathematical theory of input-output efficient preprocessing. This new theory will develop the computational tools to design powerful algorithms for preprocessing very large instances of hard problems that very efficiently compress those instances to smaller ones with guaranteed size. Our motivation is the incapability of current preprocessing routines with compression guarantee (kernelizations) to handle very large instances that do not fit into main memory. The theory also seeks to rigorously explain the practical successes of preprocessing very large instances by algorithms without compression guarantee (heuristics), and will lead to a concept of computational intractability to explain the limitations of heuristics.The project aims to design preprocessing algorithms that harness the full capabilities of advanced processor technology and memory hierarchies of computing hardware in science and industry, to efficiently compress big data sets. With new multivariate computational models that utilize instance structure and hardware structure at the same time, we will deepen the understanding of the mathematical origins of compressibility and serve to build more powerful algorithms for preprocessing massive data sets.

该项目的主要研究目标是寻求一个严格的数学理论的输入-输出有效的预处理。这个新的理论将开发计算工具来设计强大的算法，用于预处理非常大的硬问题实例，非常有效地将这些实例压缩到具有保证大小的较小实例。我们的动机是目前的预处理例程与压缩保证（内核化）处理非常大的实例，不适合到主内存的能力。该理论还试图严格解释在没有压缩保证的情况下，通过算法预处理非常大的实例的实际成功（计算机科学），并将导致计算棘手的概念，以解释计算机科学的局限性。该项目旨在设计预处理算法，利用先进的处理器技术和存储器层次结构的计算硬件在科学和工业的全部能力，来高效地压缩大数据集。通过同时利用实例结构和硬件结构的新的多变量计算模型，我们将加深对压缩性的数学起源的理解，并为建立更强大的算法来预处理海量数据集服务。

项目成果

Dynamic Parameterized Problems and Algorithms

• DOI: 10.1145/3395037
• 发表时间: 2020-09-01
• 期刊: ACM TRANSACTIONS ON ALGORITHMS
• 影响因子: 1.3
• 作者: Alman, Josh;Mnich, Matthias;Williams, Virginia Vassilevska
• 通讯作者: Williams, Virginia Vassilevska

Engineering Kernelization for Maximum Cut

• DOI: 10.1137/1.9781611976007.3
• 发表时间: 2019-05
• 作者: D. Ferizović;Demian Hespe;S. Lamm;Matthias Mnich;Christian Schulz;Darren Strash

Solving the Set Packing Problem via a Maximum Weighted Independent Set Heuristic

通过最大加权独立集启发式解决集合填充问题

• DOI: 10.1155/2020/3050714
• 发表时间: 2020-12
• 期刊: Mathematical Problems in Engineering
• 作者: Li Ruizhi;Wang Yupan;Hu Shuli;Jiang Jianhua;Ouyang Dantong;Yin Minghao
• 通讯作者: Yin Minghao

Parameterized Algorithms for Generalizations of Directed Feedback Vertex Set

• DOI: 10.1007/978-3-030-17402-6_21
• 发表时间: 2019-05
• 期刊: ArXiv
• 作者: Alexander Göke;D. Marx;Matthias Mnich

Resolving Infeasibility of Linear Systems: A Parameterized Approach

解决线性系统的不可行性：参数化方法

• DOI: 10.4230/lipics.ipec.2019.17
• 发表时间: 2019
• 作者: A. Göke;L. M. Mendoza Cadena;M. Mnich
• 通讯作者: M. Mnich