New Horizons in Multivariate Preprocessing (MULTIPROCESS)

多变量预处理 (MULTIPROCESS) 的新视野

基本信息

批准号：
EP/V044621/1
负责人：
Ramanujan Maadapuzhi Sridharan
金额：
$ 69.53万
依托单位：
University of Warwick
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2022
资助国家：
英国
起止时间：
2022 至无数据
项目状态：
未结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FV044621%2F1
关键词：
New Horizons Multivariate Preprocessing MULTIPROCESS

项目摘要

Data preprocessing or data compression is a ubiquitous strategy to cope with computational hardness in various real world applications. The goal here is to efficiently compute a succinct representation of the original data with only a small loss in the accuracy of the information represented within it. This is achieved through various steps such as simplifying the structure of the input, reducing the size or dimension, removing redundant constraints and so on.The widespread recognition of the importance of preprocessing algorithms in practice has motivated the challenging task of developing mathematical frameworks within which it is possible to conduct rigorous analysis, provide performance guarantees and compare the quality of various preprocessing algorithms proposed for specific computational problems. A partial answer to this challenge was provided in the area of parameterized complexity (or multivariate complexity) through the framework of kernels. This framework has lead to a vibrant new subfield of algorithmics -- Kernelization. The field of kernelization has turned out to be a resounding success over the last two decades as far as the analysis and understanding of 'lossless' preprocessing for NP-hard (computational problems that are not expected to have theoretically efficient, i.e., so called polynomial-time algorithms) decision problems is concerned. However, in practice, preprocessing is heavily used for large data sets of problems that have theoretically efficient (polynomial-time) algorithms as well as for NP-hard problems where one wants to optimize some objective function over the input data. In these situations, the framework of kernelization falls woefully short and does not combine well with approximation algorithms or heuristics. This proposal aims to make major advances in the mathematical theory of preprocessing by delivering new formulations of efficient preprocessing that overcome the aforementioned fundamental limitations that plague the classic theory of polynomial-time preprocessing. This project will lead to novel preprocessing heuristics and analyses for basic computational problems and extend the scope of rigorous preprocessing analysis to high-impact big data paradigms such as streaming algorithms. This will be achieved by delivering new preprocessing design techniques as well as new mathematical machinery that allows one to formally characterize the limitations of preprocessing for various problems. This project will bring about a paradigm shift by laying the foundations for a new theory of preprocessing that will be able to abstract and unify all efficient preprocessing. This is but the beginning of a timely journey into a mostly unexplored universe teeming with possibilities and undiscovered connections between diverse subfields of computer science.

数据预处理或数据压缩是一种无处不在的策略，可以应对各种现实世界应用中的计算硬度。这里的目的是有效计算原始数据的简洁表示，仅在其中表示的信息的准确性上只有很小的损失。这是通过各个步骤来实现的，例如简化输入的结构，减少大小或维度，消除冗余约束等。广泛认识到实践中预处理算法的重要性的广泛认识，激发了挑战性的任务，并为制定了多种效率的数学框架，在这些框架中进行了多种范围，可以在范围内进行特定的绩效，从而可以进行质量分析，从而可以进行质量的质量，从而可以进行质量的质量，这些范围是有效的，这些框架可以进行质量的质量，这些框架可以进行良好的效果，这是可以进行质量的，这些框架可以进行良好的效果，这是可以进行质量的，这些框架可以进行良好的质量，这些框架是有效的。问题。通过内核框架，在参数化的复杂性（或多元复杂性）领域提供了部分答案。该框架导致了一个充满活力的算法新子场 - 内核化。就过去二十年而言，对于NP-HARD的“无损”预处理（预期没有理论上有效的计算问题，即所谓的多项式时时间算法）的分析和理解，内核化领域已取得了巨大的成功。但是，实际上，预处理大量用于具有理论上有效（多项式）算法的大型数据集以及NP - 硬性问题，在这些问题中，人们希望在输入数据上优化某些目标函数。在这些情况下，内核化的框架非常短，与近似算法或启发式方法结合得很好。该提案旨在通过提供有效的预处理的新表述来取得预处理数学理论的重大进步，从而克服了上述基本限制，这些限制困扰着多项式时间预处理的经典理论。该项目将导致新的预处理启发式方法和分析基本计算问题，并将严格的预处理分析的范围扩展到高影响力的大数据范式（例如流媒体算法）。这将通过提供新的预处理设计技术以及新的数学机制来实现这一目标，该技术允许人们正式表征针对各种问题的预处理的局限性。该项目将通过为新的预处理理论奠定基础，从而带来范式转变，该理论将能够抽象和统一所有有效的预处理。这只是及时进入一个大多数未探索的宇宙的开始，这些宇宙的可能性和计算机科学各个子场之间的可能性和未发现的联系。