Return to Answer

The problem in the question

The price of product $p$ at time $t$ is $b_p{r_p}^t $, where $p$ and $t$ are integers between 1 and $n$.. We want to find a permutation $f$ of $1,2,\cdots,n$ such that $\sum_{p=1}^nb_pr_p^{f(p)}$ is minimum.

A more general problem and polynomial-time algorithms

The price of product $p$ at time $t$ is $c(p,t)$, where $p$ and $t$ are integers between 1 and $n$. We want to find a permutation $f$ of $1,2,\cdots,n$ such that $\sum_{p=1}^nc(p,f(p))$ is minimum.

The problem above is none other than the famous assignment problem. There are various polynomial-time algorithms to solve it. For example, this version of Hungarian algorithm runs in $O(n^4)$ time.

For the problem in the question, it can also be solved in polynomial time since we can compute all $b_pr_p^t$ for $1\le p, t\le n$ in $O(n^2)$ time.

What is the problem in the question?

The price of product $p$ at time $t$ is $b_p{r_p}^t $, where $p$ and $t$ are integers between 1 and $n$.. We want to find a permutation $f$ of $1,2,\cdots,n$ such that $\sum_{p=1}^nb_p{r_p}^{f(p)}$ is minimum.

A more general problem and polynomial-time algorithms

The price of product $p$ at time $t$ is $c(p,t)$, where $p$ and $t$ are integers between 1 and $n$. We want to find a permutation $f$ of $1,2,\cdots,n$ such that $\sum_{p=1}^nc(p,f(p))$ is minimum.

The problem above is none other than the famous assignment problem. There are various polynomial-time algorithms to solve it. For example, this version of Hungarian algorithm runs in $O(n^4)$ time.

For the problem in the question, it can also be solved in polynomial time since we can compute all $b_p{r_p}^t$ for $1\le p, t\le n$ in $O(n^2)$ time.

The problem in the question

The price of product $p$ at time $t$ is $b_p{r_p}^t $, where $p$ and $t$ are integers between 1 and $n$.. We want to find a permutation $f$ of $1,2,\cdots,n$ such that $\Sigma_{p=1}^nb_pr_p^{f(p)}$ is minimum.

A more general problem and polynomial-time algorithms

The price of product $p$ at time $t$ is $c(p,t)$, where $p$ and $t$ are integers between 1 and $n$. We want to find a permutation $f$ of $1,2,\cdots,n$ such that $\Sigma_{p=1}^nc(p,f(p))$ is minimum.

The problem above is none other than the famous assignment problem. There are various polynomial-time algorithms to solve it. For example, this version of Hungarian algorithm runs in $O(n^4)$ time.

For the problem in the question, it can also be solved in polynomial time since we can compute all $b_pr_p^t$ for $1\le p, t\le n$ in $O(n^2)$ time.

The problem in the question

The price of product $p$ at time $t$ is $b_p{r_p}^t $, where $p$ and $t$ are integers between 1 and $n$.. We want to find a permutation $f$ of $1,2,\cdots,n$ such that $\sum_{p=1}^nb_pr_p^{f(p)}$ is minimum.

A more general problem and polynomial-time algorithms

The price of product $p$ at time $t$ is $c(p,t)$, where $p$ and $t$ are integers between 1 and $n$. We want to find a permutation $f$ of $1,2,\cdots,n$ such that $\sum_{p=1}^nc(p,f(p))$ is minimum.

The problem above is none other than the famous assignment problem. There are various polynomial-time algorithms to solve it. For example, this version of Hungarian algorithm runs in $O(n^4)$ time.

For the problem in the question, it can also be solved in polynomial time since we can compute all $b_pr_p^t$ for $1\le p, t\le n$ in $O(n^2)$ time.

###The problem in the question###

The price of product $p$ at time $t$ is $b_p{r_p}^t $, where $p$ and $t$ are integers between 1 and $n$.. We want to find a permutation $f$ of $1,2,\cdots,n$ such that $\Sigma_{p=1}^nb_pr_p^{f(p)}$ is minimum.

###A more general problem and polynomial-time algorithms### The price of product $p$ at time $t$ is $c(p,t)$, where $p$ and $t$ are integers between 1 and $n$. We want to find a permutation $f$ of $1,2,\cdots,n$ such that $\Sigma_{p=1}^nc(p,f(p))$ is minimum.

The problem above is none other than the famous assignment problem. There are various polynomial-time algorithms to solve it. For example, this version of Hungarian algorithm runs in $O(n^4)$ time.

For the problem in the question, it can also be solved in polynomial time since we can compute all $b_pr_p^t$ for $1\le p, t\le n$ in $O(n^2)$ time.

The problem in the question

The price of product $p$ at time $t$ is $b_p{r_p}^t $, where $p$ and $t$ are integers between 1 and $n$.. We want to find a permutation $f$ of $1,2,\cdots,n$ such that $\Sigma_{p=1}^nb_pr_p^{f(p)}$ is minimum.

A more general problem and polynomial-time algorithms

The price of product $p$ at time $t$ is $c(p,t)$, where $p$ and $t$ are integers between 1 and $n$. We want to find a permutation $f$ of $1,2,\cdots,n$ such that $\Sigma_{p=1}^nc(p,f(p))$ is minimum.

The problem above is none other than the famous assignment problem. There are various polynomial-time algorithms to solve it. For example, this version of Hungarian algorithm runs in $O(n^4)$ time.

For the problem in the question, it can also be solved in polynomial time since we can compute all $b_pr_p^t$ for $1\le p, t\le n$ in $O(n^2)$ time.