Every day, computer algorithms decide the fastest delivery route, the cheapest flight, or the most efficient way to schedule a factory floor—but for many of these problems, finding the perfect answer is mathematically impossible in a reasonable time. This project tackles a fundamental gap in computer science. For decades, researchers have had to choose between two imperfect strategies: either accept a fast but approximate answer, or accept a slow but exact one. A growing class of problems—like detecting tightly connected groups in social networks or optimising complex supply chains—defeats both approaches. This work pioneers a third way: fine-grained approximation, which deliberately relaxes both constraints at once, allowing algorithms to find good-enough solutions in slightly more than standard time. If successful, the research will provide a new theoretical toolkit for problems that currently have no practical solution. The immediate impact is on fundamental computer science, establishing the mathematical foundations of this emerging field. In the longer term, these algorithms could improve the performance of navigation systems, logistics software, and network analysis tools—any system where a perfect answer is impossible but a very good one, found a little more slowly, would be a genuine advance.
View original technical description
Algorithms are ubiquitous in all aspects of our daily lives. Given their importance both on a personal and societal level, it is essential that we are able to design algorithms for fundamental computational problems which are both (i) correct and (ii) fast (i.e., running in polynomial time in the input size). However, under the well-believed hypothesis of P!=NP from theoretical computer science, it is impossible to design algorithms which achieve both these properties for most interesting real-world tasks, e.g. choosing the optimal order in which to visit a given set of destinations such that the total distance travelled is minimized. If one insists on algorithms which are guaranteed to be provably correct, then the cost must be paid in the running time which is a big (exponential) function of the input size. This can severely limit the use of algorithms in applications: for example a running time of 2N quickly becomes infeasible in practice, even for relatively small input sizes such as N=300 this exceeds the estimated number of atoms in the universe! This intractability led to the development of two areas of algorithmic research: 1. Approximation algorithms: We relax the requirement of being correct, but the algorithm is required to be fast, i.e., run in polynomial time in size of the input. 2. Fine-grained algorithms: We require the algorithm to be correct, but relax the requirement of the algorithm being fast: an additional factor is allowed in the running time which can be any function of carefully chosen parameters which capture tractability of the given problem Both of these areas are at the forefront of research in theoretical computer science with hundreds of results each year. However, there is now evidence that a large class of computational problems (e.g. Clique, Directed Multicut, etc.) are not tractable with respect to either approximation algorithms or fine-grained algorithms. For such problems, the paradigm of fine-grained approximation algorithms is a next natural step where we relax both conditions: the goal is to find approximate solutions while allowing running time which is beyond polynomial time. Although this is a nascent area of research in computer science with only a few results (mostly in the last 5-7 years), it is known that there are problems which are not amenable individually to either approximation algorithm or fine-grained algorithms but the one-two punch of fine-grained approximation algorithms leads to improved theoretical guarantees. This project has two main research objectives: 1. Develop the theoretical foundations of this hitherto unexplored paradigm of fine-grained approximation algorithms 2. Introduce this paradigm to researchers in fields beyond theoretical computer science Our project will push the boundaries of tractability in algorithms research. Additionally, we will provide practitioners with a new suite of algorithms (with improved performance guarantees) for fundamental computational problems that need to be solved in real-world applications.
Plain English summaries and category classifications on this site are generated by AI and may not perfectly reflect the original research.
Is something wrong? Let us know