Undergrad Smoothness of Discrete Functions

[The Number Juggler]

Hi Physics Forums

Is there a specific technique to measure how smooth a discrete function is?

By smooth I mean that if you change the input by a minimum amount then you know that the objective function result will not have a big jump.

For example The Closest String Problem is completely smooth function, since if you change the input string by only one letter, then the distance to the furthest string will change by at most one.

The Traveling Salesman Problem is also smooth, but not completely so. If you change only the order that you visit two cities then the total distance traveled could not change as much as if you altered more. However there could be larger and smaller jumps.

Moving around a grid of random numbers would be completely unsmooth.

I'm sure there must be another word for this phenomena and some research done already. But google is providing anything except "smoothing discrete functions" which is a completely different thing altogether!

 

[Stephen Tashi]

Hi Physics Forums

Is there a specific technique to measure how smooth a discrete function is?

By smooth I mean that if you change the input by a minimum amount then you know that the objective function result will not have a big jump.

It isn't clear what you have in mind for the domain of the function - one real variable ?, a vector of variables ?

If you want to look at methods that are analogous to those used for differentiable functions (e.g. first derivative being bounded or partial derivatives being bounded) investigate "the calculus of finite differences".

 

[pwsnafu]

The only thing I can recall is a function is from actuarial science: Barnett n-th order smooth iff $|{\Delta^n a_x}| \cdot 7^n < a_x$. But this is really for life tables.

 

[Charles Allison]

A discrete function is smooth if f(2n) = Θ(n) (theta of n). If f(2n) = o(n), it is not smooth. Source: Algorithms by Neapolitan, Appendix B.2.