Local Search and the General Assignment Problem

Add to your list(s) Download to your calendar using vCal

• Márton Havasi, Churchill College
• Wednesday 28 January 2015, 19:00-19:40
• Wolfson Hall, Churchill College.

If you have a question about this talk, please contact Jasper Lee.

What can one do when faced with an NP-hard optimisation problem? We will examine local search algorithms and their potential to approximate difficult tasks, where the best known exact algorithm has exponential time complexity. In particular, I will show how we can apply local search to give approximate solutions with bounded error to the General Assignment Problem (GAP) in polynomial time.

This talk is part of the Churchill CompSci Talks series.

This talk is included in these lists:

• Churchill CompSci Talks
• Wolfson Hall, Churchill College
• computer science
• se393's list

Note that ex-directory lists are not shown.