Search for contacts, projects,
courses and publications

Approximation Algorithms for Machine Scheduling Through Theory and Experiments

People

 

Gambardella L. M.

(Responsible)

Mastrolilli M.

(Collaborator)

External participants

Ambühl Christoph

(Third-party beneficiary)

Abstract

The two main goals of the project are the following: Approximation Algorithms: We want to address and possibly solve some of the open questions in scheduling theory which have been open for more than 20 years by now. As Schuurman and Woeginger write “Progress on any of them would be very important” and “it will trigger several breakthroughs in the near future”. Understanding Heuristic Methods: many heuristics for several problems have no worst-case guarantees on performance, but do well for “typical” problems. Understanding when and to what extent heuristic methods succeed and fail is a challenge for both theory and practice. We would like to obtain a theoretical understanding of when widely used heuristics, like Ant Colony Optimization and Tabu Search succeed.

Additional information

Start date
01.10.2003
End date
31.10.2005
Duration
25 Months
Funding sources
SNSF
Status
Ended
Category
Swiss National Science Foundation / Project Funding / Mathematics, Natural and Engineering Sciences (Division II)