TCS / Research / Publications / Optimization, block designs and No Free Lunch theorems
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science

Optimization, block designs and No Free Lunch theorems


Evan Griffiths and Pekka Orponen. Optimization, block designs and No Free Lunch theorems. Information Processing Letters, 94(2):55–61, April 2005.


We study the precise conditions under which all optimization strategies for a given family of finite functions yield the same expected maximisation performance, when averaged over a uniform distribution of the functions. In the case of bounded-length searches in a family of Boolean functions, we provide tight connections between such ``No Free Lunch'' conditions and the structure of -designs and -wise balanced designs for arbitrary values . As a corollary, we obtain a nontrivial family of -variate Boolean functions that satisfies the ``No Free Lunch`` condition with respect tosearches of length . Modifying the construction, we also obtain nontrivial ``No Free Lunch`` families of functions with large ranges.


theory of computation, combinatorial problems, optimization, No Free Lunch theorems, combinatorial designs

Suggested BibTeX entry:

    author = {Evan Griffiths and Pekka Orponen},
    journal = {Information Processing Letters},
    month = {April},
    number = {2},
    pages = {55--61},
    title = {Optimization, block designs and {N}o {F}ree {L}unch theorems},
    volume = {94},
    year = {2005},

See ...

[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 19 January 2010.