date-created: 2024-06-14 04:03:10 date-modified: 2024-06-17 03:24:55

Approximation algorithms ::

Lets say we have an optimization problem that is NP hard [[111.99_algo_ProblemComplexity]]

In this example we consider an instance I of a minimization problem.

• Denoted by OPt(I) the value of its optimal solution - eg the length of the shortest TSP tour [[111.21_algo_graphs_ShortesPathProblems]]
• Denote A(I) the value of the solution that is returned by algorithm A on instance I.

==THe approximation ratio of the algorithm A== is defined as ${\alpha }_A=ma{x}_I\frac{A(I)}{OPT(I)}$

Possible intuition :: we can guarantee that in the worst case our algorithm returns a result that deviates at most by factor $\alpha$ from the optimal solution.

It makes sense to look for an algorithm with a good approximation ratio - as close to 1 - and with small running time. If Alpha was 1 then our success-ratio would be 100% and we would always find a solution. THe more it deviates from 1 the worse our percentage of success is .

Example : Set cover - Mengenüberdeckungsproblem::

• Assume we want to determine where to build hospitals in Germany.
• We would like to achieve that nobody lives at a distance larger than 50km from a hospital
• We would like to build as few hosptials as possible.

How many circles with radius 50 do we require to cover all parts of germany ?

==Formal description of problem==:: Set-Cover-Problems : We are given a set of n elements $B=\{b_1,\dots ,b_n\}$ and a collection of subsets $S_1,\dots ,s_m\subset B$ Our Goal:: find a minimal number of subsets whose union is B.

![[Pasted image 20230116152424.png]]

Greedy algorithm - 1 ::

while there are still uncovered elements : 
	Pick the set $S_{i}$ that contains the largest number of uncovered elements

probably a bad implementation.

However the approximation ratio doesnt seem to be too bad.

===Proofing Our algorithm==

• Denote $n_0:=n$ For t $\ge 1$ define $n_t$ as the number of elements that are still NOT covered after t iterations.

• Consider the optimal covering by k subsets. There must exist at least one set $S_t$ in this covering that contains at least $\lround n_{t} / k $ of these uncovered elements. This holds true because we have to fill all points - n - into our k subsets. By considering a uniform distribution the amount of elements in each subset would be exactly $\frac{n_t}{k}$ and if that was no the case, then one subset contains more elements than the other ones. and for that case our distribution would still hold true because there exists a subset of them all that contains the given amount of elements. If that was not true, we didnt find the right solution because not all elements are covered by k subsets.

• In Particular $S_t$ is not yet part of our current covering otherwise its elements would have been ocvered already.

• So by the greedy choice, the next set that we are going to add to our selection will cover at least $\frac{n_t}{k}$ elemtns. This leads to the inequality:: $n_{t+1}\le n_t-\frac{n_t}{k}\le n_t-\frac{n_t}{k}=n_t(1-1/k)$ Applying this inequality repeatedly we obtain : $n_t\le n_0(1-1/k{)}^t$ we can continue with the inequality of exp(-1) : (1-x) <= exp(-x) gives us : $n_t\le n_0\ast exp(-t/k)$ We now know that we require $n_t$ to be smaller than 1 - can only be 0 - for us to have found the correct solution of k subsets.

We can therefore ==proof== that the approximation ratio is tight::

For any n one can contruct an instance of the et cover problem for which the greedy algorithm probably achieves a factor of no less than $logn$ >> Der Faktor ist nicht schlechter las log n. Wir müssen eine Instanz finde, um ziegen zu können, dass dass der Faktor höchstens und mindestens $logn$ ist. Wir wisssen dann, dass es nur $logn$ sein kann.

Vertex-Cover

![[Pasted image 20230116154042.png]] Given an undirected graph, find the smallest subset S of vertices such that for each edge, at least one of its end points is in S.

Possible implementations ::

==Greedy==:: We could search for the nodes with the largest nodes pointing inward, and then color those so that we’ve covered the most expensive - best located - ones.

We could use ==matching== [[111.99_algo_graphs_matching]]

Example :: Traveling salesman ::

Consider traveling salesman problem :

• Given distance matrix of pairwise distances d(i,j) between n cities. We would like to find the shortest tour that visits each city once and returns to its starting point. Wir wissen, dass TSP ein [[111.99_algo_ProblemComplexity|NP-schweres Problem ist]] We now additionally assume that the distances satisfy the triangle inequality :: $d(u,v)\le d(u,w)+d(w,v)$

If we travel from tüb to stg, then the length should be shorter than the journey from tüb, esslingen and esslingen and stg

We would like to find the lower and upper bound !

Lower Bound construction ::

• Consider any tour through the cities.
• Removing one of its edges leaves us with a cycle-free path through all cities - it is a spanning tree
  • DIes gibt uns einne Pfad durch alle Städte, aber wir kommen nicht mehr zum Anfang zurück ==> deswegen ein Spannbaum und kein TSP path
• The costs of this spanning tree are definitely lower bounded by the cost o the minimal spanning tree of the graph
  • das heißt, wenn wir für jeden Pfad den MST erstellt und genommen haben, dann haben wir definitiv ein Lower bound für unser Problem gefunden.
• ==consequently== the cost of the best TSP tour is lower bounded by the cost of the minimal spanning tree

Schließlich können wir keinen kleineren Pfad finden, da der MST diese Eigenschaft bereits abdeckt >> heißt wir müssen demnach größer sein!

Upper Bound construction ::

We now constructed a MST and set the lower bound as seen above. We can now generate the TSP based on that date ::

==Algorithm==::

• Walk along each of the edges twice and follow all of the tree.

• This results in a tour through the graph of length twice the MST costs. We call it the MST-tour

  We can assume that the TSP-Cost will definitely be lower than our double-MST-Cost

• However some vertices are visited twice by this tour, so it is not yet a valid TSP-tour. So we throw out all the ciies that we have visited twice now.

Start with any vertex in the MST. Follow the MST-tour. Whenever we encounter a vertex that has already been visited we simply skip this vertex and jump to the next unvisited vertex. This principle holds true ==because of the inequality we set before!==

![[Pasted image 20230120105730.png]] We have the given path - ==the graphs MST==. We traverse through it twice to create the upper bound. ![[Pasted image 20230120105810.png]] Now we can traverse through it once more and whenever we would visit a city twice - tulsa after visiting wichita for example - we can simply skip to the next node that is unvisited > Amarillo in that case.

![[Pasted image 20230120105948.png]]

Because of the triangle inequality, removing the edges in the tour can only decrease the costs of our tour!.

Two cases consider to be considered for proofing ::

1. removing internal loops
2. connecting start to end is better than re-tracing the whole tour.

Once we’ve applied the principle to our solution we can show a possible solution – approximated, not the best necessarily – to our TSP-problem ::

MST-costs $\le$ optimal TSP-costs $\le$ cost of our tour $\le$ 2* MST-costs

To shorten :: $\frac{costofourtour}{optimalTSP-costs}\le 2$ So this procedure results in a valid TSP tour whose costs are at most twice the MST-Cost. We found another ==2-approximation==

Note ::

This approximation only holds true if the triangle inequality holds true >> in case it does not, we could not take those assumptions. The guarantee is false in a general case but possible in this specific.

Example :: Knapsack ::

We could set another approximation for the knapsack problem ::

Consider again the knapsack problem with integer values and volumes. We now want to construct a $(1+ϵ)$-approximation of the solution, for any $ϵ>0$

Our Intuition ::

• In dynamic programming approach the running time was $\mathcal{O}(n\ast V)$ where V is the sum of the values of all objects. this is great whenever V is rather small, yet gets bad rly quick.
• ==Idea!== we could simply rescale all values by some factor –> to have V being rather small ?

==Will it help with reducing our running time, because we scale down V ?==

The catch of this approach:: To continue with integer values, we need to round after rescaling –> we will have rounding errors, ==great for approximations!== <– This will be an error regarding the result. The error will be larger if we rescale heavily >> because we lose a lot of precision.

Knapsack approximation idea ::

Formally described ::

1. Discard all items with $va{l}_i>va{l}_{total}$
2. Let all $va{l}_{max}$ that we’ve found be the maximum value among all items
3. We rescale and round all values –==round up== if we look at the weight >> create upper bound for value –==round down== if we look at the value >> create lower bound, what at least to be achieved for each i - amount of items - :: rounded value = $val_{^}:= \frac{val_{i} }{val_{max} *\frac{n}{\epsilon}}$ rounded down Here $ϵ$ is giving us insight of how well our algorithm will behave. >> we can dynamically scale it with that.
4. Now run the dynamic programming algorithm with the new values. We can obverse:
   • the Algorithm is faster if we scale drastically, yet we loose a lot of precision and create a ound
   • the algorithm is slower – maybe closer to origin - if we choose a low scale

running time:: After rescaling the total sum of values is given as sum $v^{^}$: $V^{\wedge :=}\sum _{i}va{l}^{\wedge }\le \sum _{i}n\}ϵ=n^2ϵ$

So the algorithm with the new values has running time : $\mathcal{O}(n\ast V^{\wedge )}\ge \mathcal{O}(n\ast \frac{n^2}{ϵ})=\mathcal{O}(n^3ϵ)$

Our running time is polynomial in n running time increases heavily with $ϵ$

• if we choose $ϵ$ to be rather small >> we strive for high precision and will get closer to our exact solution, yet take way longer in overall >> because precision is higher
• if we choose $ϵ$ to be rather large we gain a fast approximation, which is off by our optimal/exact solution but we are getting an approximation. Is not the best approximation yet can be further reduced after time.

Note that we deal with a maximation problem here! What we want to achieve in an $ϵ$-approximation is that the solution of the algorithm is at most factor (1-$ϵ$) away from the optimal solution. >> this equation shows that we $ϵ$ being small creates a high precision and long running times.

• Assume that the solution to the original problem is to pick items in the set S, with total value $K^{\ast }$. THe rescaled value of this solution then satisfies :: $\sum _{i\in S}va{l}^{\wedge }=\sum _{i\in S}\frac{va{l}_i\ast n}{ϵva{l}_{max}}\ge \sum _{i\in S}(\frac{va{l}_i\ast n}{ϵva{l}_{max}}-1)⟺\left(\sum i\in Sva{l}_i\right)\ast \frac{n}{ϵva{l}_{max}}-n\ge K^{\ast }\ast \frac{n}{ϵva{l}_{max}}-n$

So the solution $S^{^}$ of the new problem, if rescaled to the original values, satisfies here ::

$\sum _{i\in S^{\ast }}va{l}_i\ge \sum _{i\in S^{\ast }}va{l}_i^{\wedge }\frac{ϵva{l}_{max}}{n}$ $\ge (K^{\ast }\frac{n}{ϵva{l}_{max}}-n)\frac{ϵva{l}_{max}}{n}=K^{\ast }-ϵva{l}_{max}\ge K^{\ast }(1-ϵ)$

In the first step we can note that we have $\ge$ because of rounding up. For the last step we observe the value $K^{\ast }$ of the optimal solution is at least as large as $va{l}_{max}$ - because by definition $va{l}_{max}$ fits in the knapsack, but $va{l}_{max}$ is the maximal value we can fit in the knapsack.

Further information ::

We found :

1. For any $ϵ$ we have constructed an (1+$ϵ$)-approximation of the algorithm
2. Our running time is $\mathcal{O}(n^3/ϵ)$ –> polynomial, yet it will increase with $ϵ$

Typically we can st the amount of precision we would like to achieve in our approximation algorithm. Here our epsilon will help with that and estimate the mount of precision we are setting

Levels of approximation ::

==Can we always construct approximation algorithms?==:

Whenever we are given any NP-hard problem, can we always construct polynomial-time approximation algorithms ?

If $P=NP$ yes –> WHY ?

Otherwise the answer is no, because we could simply find a optimal solution that is relatively fast anyway.

There exist problems for which no polynomial-time approximation algorithm with polynomial approximation factor is possible at all. There are problems available that are soo hard to solve, that we cannot approximate a solution because it would take way to much time too –> also polynomial to an extent that we cannot solve it faster.

And example would be ::

1. Maximum Independent set - and independent set in a graph is a set of vertices such that no two vertices ar connected by an edge. A maximum independent set is the largest such set exists in a given graph.
2. Maximum clique problem - find the size of the max clique in a graph

for those tasks we cannot find any algorithm to create a worst case that is not slower than exponential running time >> for some instances its possible, but theoretical we cannot find a solution for the worst case of this problem.

==There exist== problems for which we can find polynomial-time algorithms with approximation ratio that slowly increass with n, example : log n but without a constant-factor approximations. An example would be : set cover.

==Constant-factor approximations== There exist problems fo which we can find polynomial-time algorithms with constant approximation factor, but i can be proved that no approximation algorithm can exit that approximates the solution better than a particular constant. Proofs for this are typically very tricky.

An example for this would be vertex cover and TSP with triangle inequality.

==Polynomial time approximation schemes==:: There exit problems whose solutions we can approximate arbitrarily well in polynomial time, we get (1+$ϵ$)-approximations for every $ϵ>0$

An example would be knapsack

The corresponding algorithms take as input the original problem and the paramater $ϵ$ and returns a solution. They are called ** polynomial time approximation schems** - PTAS. Typically the running time of such algorithms increases dramatically with $ϵ$ - why does it make sense ? because we loose/gain precision based on our choosen epsilon and thus the scaling is some what relying on this factor.

Finally, note that all these distinctions are only interesting if our Problem is $P\ne NP$

For NP-hard problems PTAS algorithms are the desired path to furhter scale down complexity and computation !