¶ Approximation Algorithms
¶ Competitive programming
¶ Introduction to Approximation Algorithms: A Human-Friendly Beginning to a Deep Journey
Competitive programming often feels like a race against time, not only in terms of how fast you can think but also in how well you can turn complex ideas into efficient, elegant solutions under pressing constraints. Many problems reward precision, exactness, and optimality—but the deeper you go, the more you realize that not every problem wants a perfect solution. Sometimes the problem itself is designed so that an exact solution would take too long, require too much memory, or stretch the boundaries of what is computationally feasible. That’s where the world of approximation algorithms quietly enters and changes the way you think about problem-solving altogether.
Approximation algorithms are not a compromise or a fallback; they’re a strategy. They open up a powerful way of dealing with problems that are theoretically impossible to solve optimally in the general case, especially within competitive programming time limits. When you understand approximation techniques well, you begin seeing the hidden structure of difficult problems, discovering patterns that help you get close to the optimal answer even without reaching it exactly. It’s like learning to navigate a dense forest without a precise map—trusting your reasoning, using guiding principles, and confidently getting close to where you need to be, rather than wandering endlessly in search of perfection.
This course of one hundred articles is going to accompany you through this entire world. It is designed to help you understand approximation algorithms the way a seasoned problem-solver understands them—not as a set of theoretical tools from formal computer science, but as practical, intuitive, immensely powerful techniques you can use in real competitive scenarios. Whether you're preparing for high-level competitions, sharpening your algorithmic reasoning, or simply expanding your mental toolkit, this journey will help you see algorithm design from an angle you may not have explored before.
The first idea to absorb is the philosophy behind approximation. In algorithmic theory, a vast number of classical problems—especially NP-hard problems—have no known polynomial-time solutions. Asking for the exact answer in these cases is like asking for perfection in a world that doesn’t allow it. But allowing “almost right” changes everything. An approximation algorithm gives a solution that is not guaranteed to be perfect but is guaranteed to be within a certain ratio of the optimal. At first glance, this might feel unsatisfying, as though settling for less. But when you explore real-world constraints, you quickly see the beauty: approximation algorithms are how complex systems stay efficient. They guide scheduling, optimization, planning, data analysis, and resource allocation in domains where perfect answers are not just difficult—they’re impractical.
In competitive programming, however, approximation algorithms are not as commonly discussed as classical dynamic programming, greedy algorithms, or graph traversal techniques. Yet when they do appear, they stand out for very specific reasons. They bring clarity to seemingly unsolvable tasks, provide fresh views on familiar problems, and often inspire clever greedy strategies, relaxed constraints, or heuristic approaches that win contests. Exploring approximation prepares your mind to break free from the idea that every problem must be solved optimally. Instead, you develop the maturity to judge when an exact solution is possible, when it's not, and when it’s better to chase a near-optimal answer intelligently.
This course begins with the intuition behind why approximation is even necessary. It’s important to understand hardness of problems—how certain problems resist polynomial-time solutions and why approximation is the most practical way to tackle them. From there, we’ll start peeling back layers of well-known NP-hard problems and explore how surprisingly simple ideas can lead to highly effective approximations. Greedy choices, randomization, relaxation of constraints, rounding strategies, leveraging combinatorial structure—all of these become tools you can wield confidently as we progress.
One of the fascinating aspects of approximation algorithms is how often the best techniques emerge from thinking differently about the same problem. Consider something like the classic Traveling Salesman Problem. In competitive programming, you almost never directly compute the perfect tour for a general graph because you'd blow past all time limits and memory boundaries. But the moment you look at approximation strategies—like doubling the minimum spanning tree and finding an Eulerian tour—you start seeing structure. You realize that optimality is sometimes less important than exploiting relationships between components. You begin seeing distances and connections in a new way. And this kind of thinking becomes extremely valuable across challenges.
Take set cover, vertex cover, scheduling, knapsack variants, graph partitioning, facility location, and clustering—problems that seem intimidating until you see the approximations that tame them. Many of these will be explored one by one throughout this course. In each case, you’ll move beyond simply memorizing facts and formulas. You’ll learn the “why” behind the approximation ratio, the “how” behind the construction, and the “what to change” when adapting the technique for a competitive setting. You’ll also see how some approximation algorithms are shockingly easy to implement, even though they come from deep theoretical ideas.
Another reason approximation algorithms matter so much is that they strengthen your ability to reason under constraints. Competitive programmers dealing with tight limits sometimes develop the habit of writing clever brute force hacks or squeezing dynamic programming states to the edge of feasibility. But approximation algorithms teach you to rethink what the problem is actually asking for. Sometimes it's not precision but feasibility that matters. Sometimes a little bit of freedom in the answer allows for a lot of creativity in the solution.
As the course progresses, you’ll dive deeper into techniques that rely on relaxing problems into linear programs, solving them efficiently, and then rounding fractional solutions back into discrete choices. Even if LPs feel theoretical, their rounding methods generate some of the most elegant approximations used in practice. The same is true for primal–dual methods, which are unpredictable at first but reveal a beautiful logic once you understand them. These methods echo through many advanced problems in competitions and interviews, and having them in your toolkit will set you apart from average problem-solvers.
Another thread running through this course will be the role of randomization. Randomized algorithms often create approximations that are surprisingly strong and beautifully simple. Randomized rounding, probabilistic guarantees, and the power of expectation will show up frequently. Learning to see randomness as a tool rather than an uncertainty is transformative. It helps you design algorithms that are fast but also statistically reliable—a combination that competitive programming prizes heavily.
Alongside these sophisticated methods, the course also touches on something often overlooked: heuristics and practical approximations used in real contests. While pure approximation algorithms have rigorous theoretical guarantees, competitive programmers often employ approximations that simply work well in practice. They use greedy choices that aren’t formally justified but consistently yield near-optimal answers in tight settings. They use local search, constructive heuristics, iterative improvement, and hybrid methods that evolve from experience and practice. These are part of the engineering side of competitive programming—one that bridges theory with real-world decision-making under stress.
Throughout these articles, you’ll learn to compare different approximation techniques, analyze when one method fits better than another, and identify the trade-offs that matter. Understanding approximation ratios is essential, but knowing what they imply in actual coding scenarios is what turns knowledge into skill. You’ll see how minor modifications in problem constraints can drastically change what approximation strategies are viable. You’ll observe how hierarchical ideas, layering of structures, and decomposition of complexity can turn large, unwieldy problems into manageable tasks.
One of the most rewarding outcomes of studying approximation algorithms is how they shift your intuition. You begin noticing patterns even in problems that do not explicitly ask for approximations. For instance, when a problem seems NP-hard, your first instinct will no longer be panic or trial-and-error. You’ll calmly think: “Is there a relaxed version? A greedy angle? A structure I can exploit? A bounded deviation from optimal that still counts?” This mindset alone elevates your competitive problem-solving ability.
Another benefit is the increased confidence you gain in dealing with large constraints. As contests evolve, problems with massive inputs are becoming more common. Exact methods strain under this weight, but approximation techniques thrive here. They help you deliver solutions that are fast, scalable, and surprisingly effective. Competitors who understand these algorithms don't just survive these problems—they excel.
Throughout this journey, you will encounter classic approximations, modern algorithms, creative techniques, and real contest examples. Approximations might feel intimidating at first, especially if you have mostly dealt with exact algorithms before. But with clear explanations, grounded intuition, and frequent connections to competitive problem patterns, each article will help you become more comfortable with the idea that “close enough” is sometimes the most intelligent, most computationally efficient, and most strategically sound answer you can produce.
By the end of this course, approximation algorithms will stop feeling like an abstract topic reserved for theoretical computer science. They will feel natural—like tools you can pick up anytime, anywhere, whenever the problem demands them. You’ll feel empowered to approach some of the toughest problems in competitive programming with a calm, logical mindset and a wider set of techniques than most programmers ever acquire.
This is not just a course about algorithms. It’s a shift in how you think. It’s an invitation to step into a new layer of algorithmic maturity, where perfection is not always the goal, but excellence still is. It’s a journey through ideas that show how much creativity, strategic relaxation, and careful reasoning can achieve—far more than brute force and rigid expectations ever could.
As you move through the hundred articles that follow, let this introduction be your starting point—a reminder that approximation is not about settling for less. It’s about navigating complexity with intelligence. It’s about choosing the path that leads you close to the summit without getting trapped in an impossible climb. It’s about understanding the heart of a problem well enough to make smart, informed decisions that get you exactly where you need to be.
Welcome to the journey. Approximation algorithms are about to reshape how you think, how you code, and how you solve problems under pressure. And once you’ve learned to see their beauty, you’ll carry that insight into every challenge you tackle—not only in competitions, but anywhere problem-solving matters.
¶ Approximation Algorithms
¶ Beginner Level
1. Introduction to Approximation Algorithms: Concepts and Motivation
2. Basics of Optimization Problems: P vs. NP
3. Approximation Ratios: Definitions and Examples
4. Greedy Algorithms: Basics and Examples
5. Greedy Algorithms for Set Cover
6. Greedy Algorithms for Knapsack Problems
7. Greedy Algorithms for Scheduling Problems
8. Greedy Algorithms for Graph Coloring
9. Greedy Algorithms for Minimum Spanning Trees
10. Greedy Algorithms for Shortest Path Problems
11. Greedy Algorithms for Maximum Cut Problems
12. Greedy Algorithms for Vertex Cover
13. Greedy Algorithms for Traveling Salesman Problem (TSP)
14. Greedy Algorithms for Bin Packing
15. Greedy Algorithms for Job Scheduling
16. Greedy Algorithms for Facility Location
17. Greedy Algorithms for Load Balancing
18. Greedy Algorithms for Network Design
19. Greedy Algorithms for Clustering
20. Greedy Algorithms for Submodular Maximization
¶ Intermediate Level
21. LP Relaxation: Basics and Examples
22. LP Relaxation for Set Cover
23. LP Relaxation for Vertex Cover
24. LP Relaxation for Knapsack Problems
25. LP Relaxation for Scheduling Problems
26. LP Relaxation for Graph Coloring
27. LP Relaxation for Minimum Spanning Trees
28. LP Relaxation for Shortest Path Problems
29. LP Relaxation for Maximum Cut Problems
30. LP Relaxation for Traveling Salesman Problem (TSP)
31. LP Relaxation for Bin Packing
32. LP Relaxation for Job Scheduling
33. LP Relaxation for Facility Location
34. LP Relaxation for Load Balancing
35. LP Relaxation for Network Design
36. LP Relaxation for Clustering
37. LP Relaxation for Submodular Maximization
38. Randomized Rounding: Basics and Examples
39. Randomized Rounding for Set Cover
40. Randomized Rounding for Vertex Cover
41. Randomized Rounding for Knapsack Problems
42. Randomized Rounding for Scheduling Problems
43. Randomized Rounding for Graph Coloring
44. Randomized Rounding for Minimum Spanning Trees
45. Randomized Rounding for Shortest Path Problems
46. Randomized Rounding for Maximum Cut Problems
47. Randomized Rounding for Traveling Salesman Problem (TSP)
48. Randomized Rounding for Bin Packing
49. Randomized Rounding for Job Scheduling
50. Randomized Rounding for Facility Location
¶ Advanced Level
51. Primal-Dual Methods: Basics and Examples
52. Primal-Dual Methods for Set Cover
53. Primal-Dual Methods for Vertex Cover
54. Primal-Dual Methods for Knapsack Problems
55. Primal-Dual Methods for Scheduling Problems
56. Primal-Dual Methods for Graph Coloring
57. Primal-Dual Methods for Minimum Spanning Trees
58. Primal-Dual Methods for Shortest Path Problems
59. Primal-Dual Methods for Maximum Cut Problems
60. Primal-Dual Methods for Traveling Salesman Problem (TSP)
61. Primal-Dual Methods for Bin Packing
62. Primal-Dual Methods for Job Scheduling
63. Primal-Dual Methods for Facility Location
64. Primal-Dual Methods for Load Balancing
65. Primal-Dual Methods for Network Design
66. Primal-Dual Methods for Clustering
67. Primal-Dual Methods for Submodular Maximization
68. Semidefinite Programming (SDP): Basics and Examples
69. SDP for Maximum Cut Problems
70. SDP for Graph Coloring
71. SDP for Traveling Salesman Problem (TSP)
72. SDP for Clustering
73. SDP for Submodular Maximization
74. SDP for Facility Location
75. SDP for Load Balancing
76. SDP for Network Design
77. SDP for Scheduling Problems
78. SDP for Knapsack Problems
79. SDP for Vertex Cover
80. SDP for Set Cover
81. SDP for Minimum Spanning Trees
82. SDP for Shortest Path Problems
83. SDP for Bin Packing
84. SDP for Job Scheduling
85. SDP for Submodular Maximization
86. SDP for Clustering
87. SDP for Facility Location
88. SDP for Load Balancing
89. SDP for Network Design
90. SDP for Scheduling Problems
91. SDP for Knapsack Problems
92. SDP for Vertex Cover
93. SDP for Set Cover
94. SDP for Minimum Spanning Trees
95. SDP for Shortest Path Problems
96. SDP for Bin Packing
97. SDP for Job Scheduling
98. SDP for Submodular Maximization
99. SDP for Clustering
100. SDP for Facility Location