Skip to main content
added 259 characters in body
Source Link
Throckmorton
  • 1k
  • 1
  • 8
  • 21

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 we describedbelow 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.

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

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 algorithm we described 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.

The algorithm is below:

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:

Source Link
Throckmorton
  • 1k
  • 1
  • 8
  • 21

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 algorithm we described 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.

The algorithm is below: