5
$\begingroup$

Let's say we have a set of products $M$, a total of $|M|=n$ that we want to buy. However, we can only buy one product at a time, so that we need a total of $n$ time-units to buy all items.

Each product $p\in M$ has a base price $b_p$, as well as an inflation rate $r_p$.
At time unit $t$, product $p$ therefore has the price $b_p \cdot {r_p}^t $.
We can assume $b_p\in \mathbb{R}$, $r_p>1$.

I'm looking for an efficient (i.e. polytime) algorithm that returns the optimal buying order which minimizes the total price.

There's an easier variant of the problem (all $b_p=1$) which can be solved using the greedy algorithm
"Always buy the one product with the highest inflation".

Given that the base prices can be vastly different, this algorithm can't be directly transferred, but knowing that an easier version of the problem had a linear-time solution, this one probably still isn't $\mathsf{NP}$-complete.

If we view every product as a function of time $p_i(t) = b_p \cdot {r_p}^t$, the greedy algorithm above tells us, that if for $t_0$ holds $p_i(t_0) = p_j(t_0)$, then from the point once $t_0$ has passed we should always pick of $p_i, p_j$ the one with the higher inflation.

I'd be open for both hints and solutions.

$\endgroup$
  • $\begingroup$ There must be a polynomial algorithm. It is just a matter of time for us to find it. $\endgroup$ – Apass.Jack Feb 20 at 15:55
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can we do better than $O(n^3)$? There is probably an algorithm in $O(n^2)$. There might be an algorithm in $O(n\log n)$. $\endgroup$ – Apass.Jack Feb 22 at 14:41
  • 1
    $\begingroup$ This was interesting from start to finish! The decomposition of the problem into the separate suproblems "calculating the prices" and "solving the allocation problem", which allows the linearization of the problem as the cost function is replaced by a look-up. Then the problem description via minimization over a symmetric group of permutations, which looks like a total dead end, having such an easy and obvious description as a linear program, and even having a further raffination! $\endgroup$ – Sudix Feb 22 at 18:50
0
$\begingroup$

some thoughts but haven't been mathematically proven. to solve the problems we need to decide the priority to buy each product

  1. if $ p_i(t) = p_j(t) $ has crossing point at $ t_{ij} > 0 $, we have two cases:
    1. when $ t < t_{ij} $ and $ p_i(t) > p_j(t) $, then we want to buy $ p_j $ sooner than $ p_i $
    2. the opposite case of 1.

this can partially define the purchase order we want for those have crossing points at $ t > 0 $

  1. to decide the purchase order of those don't have crossing point at $ t > 0 $, we can rely on their initial price $ p_i(0) $, e.g. if $ p_i(0) > p_j(0) $, we want to buy $ p_i $ before $ p_j $.

  2. the above two steps define a partial order of all the products, to finalize an optimal purchase order, we can enumerate all the tsort order of the graph(nodes are products, partial order as edges) to find the optimal purchase order.

time complexity:

solving 1. and 2. takes $ O(nlog(n)) $ (solving each exponential equations takes $ O(log(n)) $ using binary search)

solving 3. takes $ O(V+E) $ where $ V=n, E<=n^2 $

$\endgroup$
  • $\begingroup$ I am afraid I cannot understand this answer. What does it mean by "$ p_i(t) = p_j(t)$ has crossing point at $ t_{ij}$"? $\endgroup$ – Apass.Jack Feb 20 at 15:55
  • $\begingroup$ How could step 3 takes $O(V+E)$ time? It looks like more than polynomial time. $\endgroup$ – Apass.Jack Feb 20 at 19:58
  • $\begingroup$ I'm not quite figuring out 1. - if $p_i(t)>p_j(t)$, why would we want to buy $p_j$ first? I came to the inverted conclusion (and then found trouble, as the crossing points can be arbitraily close to the integers). As for 2.: Two products have no crossing point exactly iff their inflation rates are identical $\endgroup$ – Sudix Feb 21 at 6:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.