2
$\begingroup$

Just a thought I had in mind. I can use classical matrix multiplication to compute min-plus matrix multiplication. Generally speaking, considering $(n+1)^{a_{i,j}}$ for each entry and then taking the smallest value.

But what about the other way around? I want to compute classic matrix multiplication by using as a blackbox an algorithm that computes min-plus. Not really sure which ideas... (And what would be the runtime)

Improve this question
$\endgroup$
2
  • $\begingroup$ Do you allow logarithms/antilogarithms or other functions? $\endgroup$
    – Yves Daoust
    Commented Jul 24 at 8:15
  • $\begingroup$ You can emulate the $\max$ operator as $\sqrt[p]{a^p+b^p}$ with very large $p$. But I can't see how you would emulate a sum from a minimum, as one of the arguments is completely lost. $\endgroup$
    – Yves Daoust
    Commented Jul 24 at 8:20

1 Answer 1

Reset to default
1
$\begingroup$

Basically, you want to compute $\hat{c}_{i,j} = \min\limits_{k=1}^n \{a_{i,j} + b_{i,j}\}$ from a blackbox (classical matrix multiplication), which computes $c_{i,j} = \sum\limits_{k=1}^n a_{i,j} \times b_{i,j}$. So basically, we need to convert a multiplication into an addition operation and a minimum into a summation. You need to process the input elements so that the desired effect can be achieved.

Converting multiplication into an addition:

exploit the $\log$ operation

Converting the minimum into a summation:

exploit the $L_\infty$ norm

Improve this answer
$\endgroup$
1
  • $\begingroup$ If I am right, the OP wants the converse. $\endgroup$
    – Yves Daoust
    Commented Jul 24 at 8:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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