Determine aproximation factor in a greedy algorithm

Question

Suppose we have n food dishes associated to a cost c, and we have i guests such that each one of them has a certain number of preferences. We want to choose a menu such that we minimize the cost and such that at least one preference for each guest is satisfied.

I implemented an easy greedy algorithm that orders each element in respect of their $\frac{\text{# of people satisfied}}{\text{cost}}$ for example if element "a" satisfies 3 people if choose and has a cost of 10, its ratio would be $3/10$. I chose each element in a non-increasing order. Until i run out of people to satisfy.

How do i find the approximation factor for this algorithm? I think it should be around 2 since it's very similar to a greedy approach to knapsack problem, but i have no clue on how to demonstrate it.

Answer 1

So if you are not updating the #satisfied/cost ratio after every selection, this algorithm won't perform well. Let $n$ be the number of people and $m$ the number of meals. We denote the cost of meal $i$ by $w_i$. Let's say people $1...n-1$ are all satisfied by meals $1...m-1$ which all have the same cost, but person $n$ will only eat meal $m$. If the cost of meal $m$ is any more than $w_1/(n-1)$, then your algorithm will select every meal.

If we instead modify the algorithm so that after every meal selection we recalculate the ratio excluding people that have already been satisfied, we can prove that the bound is $H_d$, where $d$ is the maximum number of people that a single menu item can satisfy and $H_d$ is the $d$th harmonic number.

Consider instead framing the problem as a weighted set cover problem. Each meal $i$ covers some subset of people $S_i \subseteq \{1,...,n\}$ and has a weight $w_i$. You want to select meals such that all people are covered and the cost of the meals is minimized. The slightly modified version of your algorithm below is an $H_d$ approximation to the weighted set cover problem. The proof is rather involved and can be found in section 5.3 here. Note that $j\gets \arg\min_k\frac{w_k}{|S_k\bigcap Uncovered|}$ in the algorithm is equivalent to selecting the max in your ratio i.e.

$$\arg\min_k\frac{w_k}{|S_k\bigcap Uncovered|} = \arg\max_k\frac{|S_k\bigcap Uncovered|}{w_k}$$ The algorithm is below: