The topic of this project is the design of efficient approximation algorithms for NP-hard combinatorial optimization problems. Such problems abound in all fields of science and engineering - in fact the vast majority of interesting problems are NP-hard and therefore do not admit fast (polynomial-time), exact algorithms. However, these problems still need to be solved! This has motivated the study of algorithms which are allowed to return sub-optimal solutions (approximation algorithms), or algorithms which use more than polynomial time (exponential-time and parameterized algorithms). The two approaches are among the most well-studied topics in theoretical computer science. Both have produced many notable successes, but they have now reached their limits. In particular, thanks to advances in fine-grained complexity theory and hardness of approximation, we know that large classes of problems are hard to approximate in polynomial time and hard to solve exactly with sub-exponential or parameterized algorithms (under standard assumptions). The SEXAPPEAL project aims to overcome these barriers by adopting a unified approach for the design of algorithms for NP-hard problems. Its scientific hypothesis is that for many important optimization problems finding an almost-optimal solution requires dramatically less time than exact optimization. This hypothesis is strongly supported by preliminary results produced by our team. This early work indicates that, by combining techniques from polynomial-time approximation with exact exponential-time and parameterized algorithms, we can guarantee a solution quality unachievable in polynomial time, often coming extremely close to optimal, while investing time significantly smaller than that needed to solve a problem exactly. Our project proposes to compose in new and innovative ways the techniques which have so far been studied disjointly in the context of exponential-time and FPT algorithms, and of polynomial-time approximation. The study of such algorithms has recently attracted interest, but is still in a nascent stage. We propose a methodology that will allow us to make rapid progress, while minimizing risk, by aligning our research across three Tasks: 1. Exponential/Parameterized Approximation Algorithms for Network Optimization Problems. 2. Generic Approximation Techniques in Super-Polynomial Time. 3. Lower Bounds and Hardness of Approximation. Task 1 will focus on the design of novel algorithms for optimization problems with applications in transportation, communication, and social networks, with the goal of out-performing the best exact algorithms in terms of running time and the best approximation algorithms in terms of solution quality. This Task is an out-growth of current work and offers the potential for rapid progress. It also includes a significant emphasis on software implementations, which will allow our work to compete with state-of-the-art solutions for various optimization problems. Task 2 will focus on the distillation of the algorithmic techniques discovered in Task 1, the development of new techniques, and their precise formalization into general meta-theorems. Finally, Task 3 aims to complete the picture by providing lower bound results on approximation in the context of super-polynomial time algorithms. The project is structured in a way that minimizes risk but maximizes gain, as work is set to begin on a Task that builds upon recent advances (Task 1), and culminate into the more ambitious Tasks (2, 3) that aim to produce a complete unified theory for dealing with NP-hardness. The state-of-the art is ripe for this work and our project can be seen as the natural continuation of a line of research in which the members of our team have played central roles in recent years. Furthermore, our team includes researchers with significant expertise in all relevant fields, and is led by a PI with a well-recognized research record fitting ideally the project topic.