Beyond no free lunch: realistic algorithms for arbitrary problem classes

Marshall James; Hinton Thomas

Beyond no free lunch: realistic algorithms for arbitrary problem classes

Marshall James
, Hinton Thomas

Research output: Working paper

11 Citations (Scopus)

Abstract

We show how the necessary and sufficient conditions for the NFL to apply can be reduced to the single requirement of the set of objective functions under consideration being closed under permutation, and quantify the extent to which a set of objectives not closed under permutation can give rise to a performance difference between two algorithms. Then we provide a more refined definition of performance under which we show that revisiting algorithms are always trumped by enumerative ones.

Translated title of the contribution	Beyond no free lunch: realistic algorithms for arbitrary problem classes
Original language	English
Publisher	Department of Computer Science, University of Bristol
Publication status	Published - 2009

Bibliographical note

Other page information: -
Other identifier: 2001087

Access to Document

http://www.cs.bris.ac.uk/Publications/pub_master.jsp?id=2001087

Handle.net

Persistent link

Cite this

@techreport{d0f46eec42db494aa095c725d31d8f4f,

title = "Beyond no free lunch: realistic algorithms for arbitrary problem classes",

abstract = "We show how the necessary and sufficient conditions for the NFL to apply can be reduced to the single requirement of the set of objective functions under consideration being closed under permutation, and quantify the extent to which a set of objectives not closed under permutation can give rise to a performance difference between two algorithms. Then we provide a more refined definition of performance under which we show that revisiting algorithms are always trumped by enumerative ones.",

author = "Marshall James and Hinton Thomas",

note = "Other page information: - Other identifier: 2001087",

year = "2009",

language = "English",

publisher = "Department of Computer Science, University of Bristol",

type = "WorkingPaper",

institution = "Department of Computer Science, University of Bristol",

}

TY - UNPB

T1 - Beyond no free lunch: realistic algorithms for arbitrary problem classes

AU - James, Marshall

AU - Thomas, Hinton

N1 - Other page information: - Other identifier: 2001087

PY - 2009

Y1 - 2009

N2 - We show how the necessary and sufficient conditions for the NFL to apply can be reduced to the single requirement of the set of objective functions under consideration being closed under permutation, and quantify the extent to which a set of objectives not closed under permutation can give rise to a performance difference between two algorithms. Then we provide a more refined definition of performance under which we show that revisiting algorithms are always trumped by enumerative ones.

AB - We show how the necessary and sufficient conditions for the NFL to apply can be reduced to the single requirement of the set of objective functions under consideration being closed under permutation, and quantify the extent to which a set of objectives not closed under permutation can give rise to a performance difference between two algorithms. Then we provide a more refined definition of performance under which we show that revisiting algorithms are always trumped by enumerative ones.

M3 - Working paper

BT - Beyond no free lunch: realistic algorithms for arbitrary problem classes

PB - Department of Computer Science, University of Bristol

ER -

Beyond no free lunch: realistic algorithms for arbitrary problem classes

Abstract

Bibliographical note

Access to Document

Handle.net

Fingerprint

Cite this