权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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-Hard问题，预处理被大量使用。在这些情况下，核心化的框架严重不足，并且不能很好地与近似算法或启发式算法相结合。这一建议旨在通过提供有效的预处理的新公式来克服上述困扰多项式时间预处理的经典理论的基本限制，从而在预处理的数学理论方面取得重大进展。该项目将导致新的预处理启发式方法和基本计算问题的分析，并将严格的预处理分析的范围扩展到高影响的大数据范例，如流算法。这将通过提供新的预处理设计技术以及允许人们正式表征各种问题的预处理的限制的新的数学机制来实现。该项目将通过为能够抽象和统一所有有效的预处理的新的预处理理论奠定基础，从而带来范式的转变。这只是一个及时的旅程的开始，进入一个基本上没有被探索的宇宙，这个宇宙充满了可能性，以及计算机科学不同子领域之间尚未发现的联系。