Centre for Discrete and Applicable Mathematics

 CDAM Research Report, LSE-CDAM-2003-02

January 2003


Links Between Learning and Optimization: A Brief Tutorial

Martin Anthony

Abstract

This report is a brief exposition of some of the important links between machine learning and combinatorial optimization. We explain how efficient `learnability' in standard probabilistic models of learning is linked to the existence of efficient randomized algorithms for certain natural combinatorial optimization problems, and we discuss the complexity of some of these optimization problems.


A PDF file (127 kB) with the full contents of this report can be downloaded by clicking here.

Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSE-CDAM-2003-02, together with your name and postal address to:
CDAM Research Reports Series
Centre for Discrete and Applicable Mathematics
London School of Economics
Houghton Street
London WC2A 2AE, U.K.
Phone: +44(0)-20-7955 7732.
Fax: +44(0)-20-7955 6877.
Email: info@maths.lse.ac.uk


Introduction to the CDAM Research Report Series.
CDAM Homepage.


Copyright © London School of Economics & Political Science 2005

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html