I'm writing a paper in which I designed an algorithm running in $O(n^2m)\cdot T(f)$ to solve my problem, where $n,m$ is the size of input and $f:\mathbb{R}\rightarrow \mathbb{R}$ is a function, and $T(f)$$ is the time to compute

$$\arg\min_{x\in [a,b]} pf(x)+qx$$

for any $a,b\in \mathbb{R}$ such that $a<b$, any any integers $1 \le p \le n, |q|\le n$.

I want the function $f$ to be as general as possile, but obviously for some function it can be unreasonably hard to solve. An approximation solution of the minimization is NOT accepted because the property of my problem.

In order to saftely claim that my algorithm runs in polynomial time for any function $f(\cdot)$, I made the following assumption in my writing:

To keep our exposition as general as possible, we assume that there is an oracle that computes $f(x)$ for a given $x\in \mathbb{R}$ and for any integer $p,q$, finds the minimum of $pf(x)+qx$ in a given interval.

I want the readers to focus on the algorithm and not to be distracted by the factor $T(f)$. Is there better way to deal with this situation? I believe someone else has also encountered this situation.


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.