Randomized and Approximation Algorithms TODO
Concept
Many combinatorial optimization problems are exactly expressed as integer programs (IP) with 0/1 variables, but IP itself is NP-hard. LP relaxation loosens that integrality constraint to the real interval [0, 1] so an optimal solution can be found in polynomial time, and the relaxed optimum gives a bound (a lower or upper bound) on the true problem's optimum. Randomized rounding takes the fractional solution x_i obtained that way and interprets it as "the probability of selecting i," then flips independent coins to round it back to an integer solution. Working out the expectation and applying concentration inequalities to show the result lands within some factor of the LP optimum is what proves the approximation ratio. The integrality gap — the worst-case ratio between the relaxed optimum and the true integer optimum — sets the ceiling on the approximation ratio this approach can ever reach.
Real-world scheduling, batching, and matching problems are mostly NP-hard, so insisting on the exact optimum simply doesn't scale — you need a basis for deciding when an approximate solution with a performance guarantee is acceptable. The LP relaxation value also gives you a free baseline for measuring how far a heuristic solution is from optimal.
Code & Formula
# Day 14: 랜덤화·근사 알고리즘 — LP 완화 + 랜덤 라운딩으로 Set Cover 근사
# 정수계획을 LP로 완화해 얻은 분수해를 확률로 삼아 반복 라운딩하면 근사 정수해를 얻는다.
import random
universe = set(range(1, 7))
sets = {"S1": {1, 2, 3}, "S2": {3, 4, 5}, "S3": {5, 6, 1}}
# 대칭 인스턴스: 원소마다 정확히 2개 집합이 덮으므로 x_S=0.5는 LP 완화의 실행가능(대칭적 최적) 분수해
x = {name: 0.5 for name in sets}
lp_value = sum(x.values())
def greedy_cover(sets, universe):
remaining, chosen = set(universe), []
while remaining:
best = max(sets, key=lambda s: len(sets[s] & remaining))
chosen.append(best)
remaining -= sets[best]
return chosen
def randomized_round(sets, x, universe, rng, max_rounds=30):
covered, chosen, rounds = set(), set(), 0
while covered != universe and rounds < max_rounds:
rounds += 1
for name in sets:
if rng.random() < x[name]:
chosen.add(name)
covered = set().union(*(sets[s] for s in chosen)) if chosen else set()
return chosen, rounds
rng = random.Random(7)
greedy = greedy_cover(sets, universe)
rounded, rounds = randomized_round(sets, x, universe, rng)
print(f"LP 완화 하한(분수 비용) = {lp_value}")
print(f"그리디 정수해 = {greedy} (비용 {len(greedy)})")
print(f"랜덤 라운딩 결과 = {sorted(rounded)} (비용 {len(rounded)}, {rounds}회 반복 후 커버 완료)")
print(f"전체 원소 커버 확인 = {set().union(*(sets[s] for s in rounded)) == universe}")
docs/code/algorithms/algorithms-14.py
Exercise
Solve a set cover instance's LP relaxation with a solver, use the fractional solution as probabilities to run randomized rounding O(log n) times, and compare the resulting cost against a greedy solution and the LP lower bound.
Practical Connection
Backend problems involving discrete choices — batch-auction matching, node/relay placement, indexer shard allocation — reuse exactly this pattern: compute an LP lower bound and use it to evaluate a heuristic.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.