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.
Where it lands in Jayverse
- OFA: log the LP-relaxation bound next to every solver result in the intent auction. Computing that lower bound for each batch turns "the solver did fine" into a measured approximation ratio instead of a feeling.
- Verex: if a heuristic batch-matcher is ever built, gate its approximation ratio against the LP bound in tests. Use the free baseline this PoC describes to fail a heuristic that drifts too far from optimal, rather than trusting it on inspection.
- gitboard: track the gap between heuristic output and the LP bound as a metric. A widening gap over time is a concrete signal that the matching or auction heuristic needs retuning.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| loosen (a constraint) | (제약을) 완화하다 · 엄격한 조건을 풀어서 문제를 다루기 쉽게 만들 때. "LP relaxation loosens that integrality constraint" |
| insist on | ~을 고집하다 · 굳이 완벽한 해답만 요구할 때. "insisting on the exact optimum simply doesn't scale" |
| set the ceiling on | ~의 상한을 정하다 · 어떤 값이 넘을 수 없는 한계를 결정할 때. "sets the ceiling on the approximation ratio" |
| a free baseline | 공짜로 딸려오는 비교 기준 · 별도 노력 없이 얻어지는 기준선. "gives you a free baseline for measuring" |
| round back to | 다시 반올림하여 되돌리다 · 소수 값을 정수 해로 되돌릴 때. "round it back to an integer solution" |
| reuse this pattern | 이 패턴을 그대로 재사용하다 · 같은 해결 방식을 다른 문제에도 그대로 적용할 때. "reuse exactly this pattern" |
| IP | 정수계획법(Integer Program) · 변수가 0/1 등 정수로 제한된 최적화 문제, 그대로는 NP-hard. "expressed as integer programs (IP) with 0/1 variables" |
| LP | 선형계획법(Linear Program) · 정수 제약을 완화해 다항시간에 풀 수 있게 만든 최적화 형태. "LP relaxation loosens that integrality constraint" |
| NP | 비결정 다항시간(Nondeterministic Polynomial time) · "NP-hard"로 쓰여 다항시간에 풀기 어려운 문제 부류를 가리킴. "IP itself is NP-hard" |
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/.