Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, December 09, 2003, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Simone Croci
We will talk about the combinatorial optimization, in which a finite set of solutions is to be analyzed in order to find a globally optimal solution. A particular way to attack the problem consists in superimposing a neighborhood structure to the combinatorial optimization problem and in computing a special solution called local optimum, which fulfills the optimality criterion at least with respect to its neighborhood. The talk will focus on finding an approximately local optimum or epsilon local optimum. One of the main results states an epsilon local optimum can be computed in polynomial time for the class of problems known as PLS (polynomial local search).
Reference: J. Orlin, A. Punnen and A. Schulz, Approximate Local Search in Combinatorial Optimization. Working Paper, MIT Sloan School of Management, 2003. To appear in SODA 2004.
Automatic MiSe System Software Version 1.4803M | admin login