Approximation Algorithms
What do you do when a problem is NP-complete?
or, when the “polynomial time solution” is impractically slow?
consider special cases
assume input is random, do “expected performance.” Eg, Hamiltonian path in all graphs. Problem: agreeing on good distribution.
run a nonpolynomial (hopefully only slightly) algorithms such as branch and bound. Usually no proven bound on runtime, but sometime can.
settle for heuristic, but prove it does well enough (our focus)
Definitions:
optimization problem, instances \(I\), solutions \(S(I)\) with values \(f:S(I) \rightarrow R\)
maximization/minimization: find solution in \(S(I)\) maximizing/minimizing \(f\)
called OPT\((I)\)
eg bin-packing. instance is set of \(s_i \in {0,1}\), partition so no subset exceeds 1
Techincal assumptions we’ll often make:
assumption: all inputs and range of \(f\) are integers/rationals (can’t represent reals, and allows, eg, LP, binary search).
assumption \(f(\sigma)\) is a polynomial size (num bits) number (else output takes too long)
look for polytime in bit complexity
NP-hardness
optimization NP-hard if can reduce an NP-hard decision problem to it
(eg, problem of “is opt solution to this instance \(\le k\)?”)
but use more general notion of turing-reducibility (GJ).
Approximation algorithm:
any algorithm that gives a feasible answer
eg, each item in own bin.
of course, want good algorithm. How measure?
Absolute Approximations
Definition: \(k\)-abs approx if on any \(I\), have \(|A(I)-OPT(I)| \le k\)
Example: planar graph coloring.
NP-complete to decide if 3 colorable
know 4-colorable
easy to 5-color
Ditto for edge coloring: Vizing’s theorem says opt is \(\Delta\) or (constructive) \(\Delta+1\)
Known only for trivial cases, where opt is bounded by a constant.
Often, can show impossible by “scaling” the problem.
EG knapsack.
define profits \(p_i\), sizes \(s_i\), sack \(B\)
wlog, integers.
suppose have \(k\)-absolute
multiply all \(p_i\) by \(k+1\), solve, scale down.
EG independent set (clique)
\(k+1\) copies of \(G\)
Relative Approximation
Definitions:
An \(\alpha\)-optimum solution has value at most \(\alpha\) times optimum for minimization, at least \(1/\alpha\) times optimum for maximization.
an algorithm has approximation ratio \(\alpha\) if on any input, it outputs an \(\alpha\)-approximate feasible solution.
called an \(\alpha\)-approximation algorithm
How do we prove algorithms have relative approximations?
Can’t describe opt, so can’t compare to it
instead, comparison to computable lower bounds.
Greedy Algorithms
Do obvious thing at each step.
Hard part is proving it works.
Usually, by attention to right upper/lower bound.
Max cut
Upper bound trivial
Max-cut greedy.
Set cover
\(n\) items
\({\mbox{OPT}}=k\)
At each step, can still cover remainder with \(k\) sets
So can cover \(1/k\) of remainder
Vertex cover:
define problem
suppose repeatedly pick any uncovered edge and cover: \(O(log n)\) from set cover
suppose pick uncovered edge and cover both sides: 2-approx
sometime, need to be extra greedy
Explicit attention to where lower bound is coming from—lower bound informs algorithm.
Graham’s rule for \(P||C_{\max}\) is a \(2-\frac1m\) approximation algorithm
explain problem: \(m\) machines, \(n\) jobs with proc times \(p_j\), min proc time.
can also think of minimizing max load of continuously running jobs
use a greedy algorithm to solve
proof by comparison to lower bounds
first lower bound: average load: \({\mbox{OPT}}\ge \frac1m\sum p_j\)
second lower bound: \({\mbox{OPT}}\ge \max p_j\)
consider max-load machine
load before adding was less than average load, so less than OPT
then add one job, length less than OPT
so final weight is at most 2OPT
Tighter: suppose added last-finishing/tight \(p_j\) to machine with load \(L\)
Then average load is at least \(L+p_j/m \le {\mbox{OPT}}\)
We achieve \[\begin{aligned} L+p_j &= (L+p_j/m) + p_j(1-1/m)\\ &\le {\mbox{OPT}}+(1-1/m){\mbox{OPT}}\\ &=(2-1/m){\mbox{OPT}}\end{aligned}\]
Notice:
this algorithm is online, competitive ratio \(2-\frac1m\)
we have no idea of optimum schedule; just used lower bounds.
we used a greedy strategy
tight bound: consider \(m(m-1)\) size-1 jobs, one size-\(m\) job
where was problem? Last job might be big
LPT achieves 4/3, but not online
Scheduling Theory
General notation: machines \(\mid\) constraints/features \(\mid\) objective
\(m\) machines \(i\) (and \(n\) jobs \(j\))
\(1\): \(1\) machine
\(P\): \(m\) identical machines
\(Q\): \(m\) machines of different speeds, but all related
\(R\): \(m\) unrelated machines, may have completely different runtimes on same jobs
\(F\): Flow shop (job is specific sequence of tasks on many machines)
\(O\): Open shop (job is specific set of tasks on many machines)
Objectives
\(\sum C_j\) average (total) completion time
\(\max C_j\) time to complete whole set
\(\sum U_j\) number of “late” jobs (post deadline)
Constraints
\(p_j=1\) unit time tasks
\(r_j\) release dates before which jobs cannot run
\(d_j\) deadlines to complete
pmtn jobs can be preempted/interrupted
prec precedence constraints on jobs
Approximation Schemes
So far, we’ve seen various constant-factor approximations.
What is best constant achievable?
defer APX-hardness discussion until later
An approximation scheme is a family of algorithms \(A_\epsilon\) such that
each algorithm polytime
\(A_\epsilon\) achieve \(1+\epsilon\) approx
But note: runtime might be awful as function of \(\epsilon\)
FPAS, Pseudopolynomial algorithms
Knapsack example.
Dynamic program for bounded integer profits
\(B(j,p)=\) smallest (total size) subset of jobs \(1,\ldots,j\) of total profit \(\ge p\).
because if can achieve it, can achieve it at minimum size
and now we have sub-problem optimality for dynamic program
\(B(j+1,p) = \min \left( B(j,p),\quad s_{j+1}+B(j,p-p_{j+1}) \right)\)
For each \(p\), solve all \(n\) values of \(j\)
Gives runtime \(nP_{{\mbox{OPT}}}\)
did this prove \(P=NP\)?
No
recall pseudopoly algorithms \(O(mU)\)
contrast to weakly polynomial \(O(m\log U)\)
rounding
Let opt be \(P\).
Scale prices to \(\lfloor (n/\epsilon P) p_i \rfloor\)
New opt is it least \(n/\epsilon-n = (1-\epsilon)n/\epsilon\)
so seek solution of this value
Table size/runtime \(n^2/\epsilon\) (\(n\) items, range \(n/\epsilon\))
Gives solution within \(1-\epsilon\) of original opt
Wait, how do we know \(P\)?
simple option: use a lower bound on \(P\), namely \(\max p_i\)
then opt scales to \((n/\epsilon \max p_i)(\sum p_i) < n^2/\epsilon\)
just slows algorithm to \(n^3/\epsilon\)
Faster: suppose we guess \(P>{\mbox{OPT}}/(1-\epsilon)\)
OPT scales to at most \((n(1-\epsilon)/\epsilon P){\mbox{OPT}}< n/\epsilon-n\)
scaled solution of desired value \(n/\epsilon-n\) doesn’t exist
so won’t find
Suppose we guess \(P<{\mbox{OPT}}\)?
OPT will scale to at least \(n/\epsilon-n\)
so will find solution of this value
possibly much less than \({\mbox{OPT}}\), but that’s ok
Of two cases, outcome tells us whether we guessed \(P\) too high or low
so, can use binary search to find \(P\)
note once we are close—\(P<OPT<P/(1-\epsilon)\)—unclear which outcome happens
but that’s OK, because we are close
quickly get within \((1-\epsilon)\) of \(P\)
adds another \((1-\epsilon)\) factor to approximation ratio
but that gives \((1-\epsilon)^2 \approx 1-2\epsilon\)
so just changes the constant.
wait, need initial low and high values?
lower bound? \(\max p_i\)
upper bound? \(\sum p_i\)
ratio of \(n\)
so, look at powers of \((1+\epsilon)\) in that range
\(\log_{1+\epsilon}n = (\log n)/\epsilon\) of them
gives a solution within \((1+\epsilon)\)
pseudopoly gives FPAS; converse almost true
Knapsack is only weakly NP-hard
strong NP-hardness (define) means no pseudo-poly
From FPAS to pseudo poly:
Suppose input instance has integers bounded by \(t\)
Solution value is \(O(nt)\)
Find \(\epsilon\)-approx with \(\epsilon=1/(nt+1)\)
Solution will be integer, so equal optimum.
Enumeration
More powerful idea: \(k\)-enumeration
Return to \(P || C_{\max}\)
Schedule \(k\) largest jobs optimally
scheduling remainder greedily
analysis: claim \(A(I) \le OPT(I)+p_{k+1}\)
Consider job with max \(c_j\)
If one of \(k\) largest, done and at opt
Else, was assigned to min load machine, so \(c_j \le OPT+p_j \le OPT+p_{k+1}\)
so done if \(p_{k+1}\) small
but note \(OPT(I) \ge (k/m)p_{k+1}\)
deduce \(A(I) \le (1+m/k)OPT(I)\).
So, for fixed \(m\), can get any desired approximation ratio
i.e., PAS
Scheduling any number of machines
As with Knapsack, focus on decision problem
Can I complete all in time \(T\)?
If can answer this, binary search will optimize \(T\)
Again, need \(T_{\min}\) and \(T_{\max}\) but these are easy
Combine enumeration and rounding
Suppose only \(k\) job sizes
Vector of “number of each type” on a given machine—gives “machine type”
Only \(n^k\) distinct vectors/machine types
Similarly, only \(n^k\) problem instances
find out which instances are feasible with \(m\) machines
By deciding how many of each machine type.
Use dynamic program:
enumerate all input instances that can be completed by \(j\) machines in time \(T\)
Feasible instance is sum of feasible \(j-1\) machine instance and 1-machine instance (machine type)
Works because only poly many instances and types.
Use rounding to make few important job types
Guess OPT \(T\) to within \(\epsilon\) (by binary search)
All jobs of size exceeding \(\epsilon T\) are “large”
Round each up to next power of \((1+\epsilon)\) in range \(\epsilon T \ldots T\)
Only \(\log_{1+\epsilon}1/\epsilon = O(1/\epsilon \ln 1/\epsilon)\) large types
Solve optimally
Greedy schedule remainder
If last job to finish is large, are optimal for rounded problem so within \(\epsilon\) of opt
If last job small, greedy analysis showes we are within \(\epsilon\) of opt.
Hardness
Is there always a PAS?
MAX-SNP hard: some unbeatable constant
Numerous problems in class (vertex cover, independent set, etc)
Amplifications can prove no constant.
Relaxations
So far we’ve seen two techniques:
Greedy: do the obvious
Dynamic Programming: try everything
Can we be more clever?
TSP
Requiring tour: no approximation (finding hamiltonian path NP-hard)
Undirected Metric: MST relaxation 2-approx, christofides
recent progress has gotten below 3/2
Directed: Cycle cover relaxation (HW) gives \(O(\log n)\)
recent progress: \(O(\log n / \log\log n)\)
Also, Euclidean TSP and planar graph TSP has PAS
intuition: SPT for \(1||\sum C_j\)
suppose process longer before shorter
then swap improves
note haven’t shown local opt implies global opt
rather, have relied on global opt being local opt
\(1 | r_j | \sum C_j\)
NP-hard
relaxation: allow preemption
optimum: SRPT
assume no \(r_j\): claim SPT optimal
proof: local optimality argument
consider swapping two pieces of two jobs
suppose currently processing \(k\) instead of SRPT \(j\)
remaining times \(p_j\) and \(p_k\)
total \(p_j+p_k\) time
use first \(p_j\) to process \(j\), then do \(k\)
some job must finish at \(p_j+p_k\)
and no job can finish before \(p_j\)
so this is locally optimal (for these 2 jobs)
rounding: schedule jobs in preemptive completion order
take preemptive schedule and insert \(p_j\) time at \(C_j\)
now room to schedule nonpreemptively
how much does this slow down \(j\)?
\(p_k\) space inserted before \(j\) for every job completing before \(j\) in preemptive schedule
in other words, only inserted \(C_j\) time
so \(j\) completes in \(2C_j\) time
so 2-approx
More recently: rounding, enumeration gives PAS
LP relaxations
Three steps
write integer linear program
relax
round
Vertex cover
\[\begin{aligned} &\min \sum x_i\\ x_i+x_j &\ge 1& (i,j)\in E\\ x_i&\in{0,1}\end{aligned}\]
Rounding
At least one end of edge \(\ge 1/2\)
round up to 1
others to 0
each vertex at most doubles
so 2-approx
this is tight (Nemhauser-Trotter)
Even weighted (unlike greedy).
Approximation hardness:
7/6 Hastad 2001
\(10\sqrt{5} -21 \approx 1.3606\ldots\) Dinur Safra 2002
\(\sqrt{2}\) Khot Minzer Safra 2017
\(2\) if unique games conjecture is true
\(2-O(1/\sqrt{\log n})\) achieved (and useful).
Facility Location
Metric version, with triangle inequality.
general version as hard as set cover.
ILP \[\begin{aligned} &\min \sum f_iy_i + \sum c_{ij}x_{ij}\\ x_{ij} &\le y_i\\ \sum_i x_{ij} &\ge 1\end{aligned}\]
Step 1: filtering
Want to assign \(j\) to one of its “partial” assignments \(x_{ij}>0\)
\(C_j = \sum_i x_{ij}c_{ij}\) is “average” assignment cost
and is amount accounted for in fractional optimum
but some \(x_{ij}>0\) may have huge \(c_{ij}\)
which wouldn’t be accounted for
rely on “can’t have everything above average”
claim at most \(1/\rho\) fraction of assignment can have \(c_{ij}>\rho C_j\)
if more, average exceeds \((1/\rho)(\rho C_j)=C_j\), impossible
so, zero out an \(x_{ij}\) with \(c_{ij} \ge \rho C_j\)
and compensate by scaling up other \(x_{ij}\) by \(1/(1-1/\rho)\) factor
Also have to increase \(y_i\) by \(1/(1-1/\rho)\) factor to “make room”
New feasible solution to LP
no longer necessarily optimal
Now, assignment of client \(j\) to any nonzero \(x_{ij}\) costs at most \(\rho C_j\)
So, total assignment cost at most \(\rho\sum C_j\)
Step 2: Facility opening: intuition
To assign, need to open facilities
If \(y_i\) small, opening facility isn’t paid for
So, find a cluster of facilities of total \(y_i > 1\)
Open minimum cost facility
Cost \(f_{\min}\le f_{\min}\sum y_i = \sum f_{\min}y_i \le \sum f_i y_i\) so LP upper bounds cost
Everything in cluster nearby, so using opened facility as “proxy” for all others without adding much cost
Step 2: Facility opening: details
Choose client with minimum \(C_j\)
Take all his “available” facilities (\(c_{ij} < \rho C_j\))
Open the cheapest and zero the others
So cost at most \(\sum f_i y_i\) over \(i\) in cluster
assign every client that has nonzero \(x_{ij}\) to any node in cluster
cost of assigning \(j'\)
\(\le \rho C_{j'}\) to reach its nonzero \(x_{i'j'}\) in cluster
then distance from \(i'\) to \(i\) is at most \(2\rho C_j \le 2\rho C_{j'}\) by choice of \(j'\)
so total \(3\rho C_j\) by metric property
Now iterate
Combine:
multiplied \(y_i\) by \(1/(1-1/\rho)=\rho/(\rho-1)\)
multiplied assignment costs by \(3\rho\)
note \(x_{ij}\) are used only to identify “feasible” facilities to connec to
so assignment cost not affected by scaling up \(x_{ij}\)
for balance, set \(\rho=4/3\) and get 4-approx
other settings of \(\rho\) yield bicriteria approximation trading facility and connection approximation costs
Further research progress has yielded
1.5-approximation
.463-hardness result.
Other algorithms based on greedy and local search.
MAX SAT
Define.
literals
clauses
NP-complete
random setting
achieve \(1-2^{-k}\) (k is the number of literals in each clause)
very nice for large \(k\), but only \(1/2\) for \(k=1\)
LP \[\begin{aligned} \max &&\sum z_j\\ \sum_{i \in C_j^+} y_i + \sum_{i \in C_j^-} (1-y_1) &\ge &z_j\end{aligned}\]
Analysis
\(\beta_k = 1-(1-1/k)^k\). values \(1,3/4,.704,\ldots\)
Random round \(y_i\)
Lemma: \(k\)-literal clause sat w/pr at least \(\beta_k {\hat z}_j\).
proof:
assume all positive literals.
prob \(1-\prod(1-y_i)\)
maximize when all \(y_i={\hat z}_j/k\).
Show \(1-(1-{\hat z}/k)^k \ge \beta_k {\hat z}\).
at \(z=0,1\) these two sides are equal
in between, right hand side is linear
first deriv of LHS is \((1-z/k)^k=1\) at \(z=0\); second deriv is \(-(1-1/k)(1-z/k)^{k-2}<0\)
so LHS cannot cross below and then return, must always be above RHS
Result: \((1-1/e)\) approximation (convergence of \((1-1/k)^k\))
much better for small \(k\): i.e. \(1\)-approx for \(k=1\)
LP good for small clauses, random for large.
Better: try both methods.
\(n_1,n_2\) number in both methods
Show \((n_1+n_2)/2 \ge (3/4)\sum {\hat z}_j\)
\(n_1 \ge \sum_{C_j \in S^k} (1-2^{-k}){\hat z}_j\)
\(n_2 \ge \sum \beta_k {\hat z}_j\)
\(n_1+n_2 \ge \sum (1-2^{-k}+\beta_k) {\hat z}_j \ge \sum \frac32{\hat z}_j\)