rhezo's blog

Does this cost function satisfy quadrangle inequality?
By rhezo, history, 7 years ago, In English

Suppose I have a cost function w(i, j) whose value depends on some f(j) and value of w(i, j) increases as |j — i + 1| increases. Also we can't compare between w(i, j) and w(p, q) even when |j — i| = |q — p| since that depends upon f(j) and f(q).

The cost function of land aquisition problem from USACO is similar and in the below link it claims that it satisfies quadrangle inequality. Check problem link from example 2 in below link.

https://sites.google.com/site/ubcprogrammingteam/news/1d1ddynamicprogrammingoptimization-parti

So, does my original cost function satisfy quadrangle inequality? I'm confused!

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Could you maybe link the question? Or any official or informal problem statement?

Edit : I am asking for the link of original problem which is similar to USACO problem.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I heard the term quadrangle inequality for the first time while reading the famous DP optimisation blog on CF. So while reading the link mentioned in blog, I couldn't understand why it satisfies quadrangle inequality.

    → Reply