Given the function

$g(n,m)=\min\Big\{f(a,b)+f(n-a,c)+f(n,m-bc)\Big|\\a,b,c\ \ \text{with} \left\{\begin{matrix} a,\ b,\ n-a,\ c,\ m-bc \geq 0 \\ b\leq a! \\ c\leq (n-a)! \\ \end{matrix}\right. \Big\} $

Assuming that $n,m\geq 0,\ ((\lceil n/2\rceil)!)^2\leq m\leq n!,\ f(n,m)=\Omega (n)$,

is it true that $g(n,m) \geq 2f(\lfloor n/2\rfloor ,(\lfloor n/2\rfloor)!)+f(n,m-((\lceil n/2\rceil)!)^2)$ ?

I tried KKT conditions, but can't derive this (as it contains factorial).

Also, it seems that the condition $f(n,m)=\Omega (n)$ implies that $f$ is convex on our domain (and thus, satisfies the regularity condition for using KKT), but I managed to prove it only if $f$ is polynomial.

So I am fully stuck in this...

Any help would be highly appreciated!

  • $\begingroup$ I'm not sure whether it makes sense to write for $f(n,m) = \Omega(n)$ for $n,m$ in some range; asymptotic analysis relates to what happens if we let $n$ and $m$ go to infinity, and your range upper-bounds $m$ so it can't go to infinity independent of $n$, and so $n$ can't go to infinity independent of $m$. Also, asymptotic notation with respect to two variables is not entirely well-defined; I don't know if that introduces any issues here. See cs.stackexchange.com/q/3149/755. $\endgroup$ – D.W. May 3 at 15:37
  • $\begingroup$ The Gamma function extends factorial to a real analytic function (which in particular has derivatives of all order). $\endgroup$ – Yuval Filmus May 3 at 23:58

Your Answer

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

Browse other questions tagged or ask your own question.