EURO Summer Institute 2010
(Geplaatst op 11 Maart 2010 om 08:10)
Austria, August 20 – September 4, 2010
Nonlinear Methods in Combinatorial Optimization
Deadline for application: Monday 15 March


website: http://www.euro-online.org/display.php?pageid=1460

Aims and Scope

Nonlinear methods such as semidefinite optimization or eigenvalue optimization have been successfully applied in the last decade to deal with NP-hard combinatorial optimization problems. A prominent example is furnished by the theta function, introduced by Lovasz (1979), which is a tractable graph parameter separating the clique number from the chromatic number. It can be formulated either in terms of eigenvalue optimization or as the optimal solution of a semidefinite program. Consequently, techniques from convex optimization are increasingly used in combinatorial optimization. On the algorithmic side, this is mostly due to the generalization of the interior-point methodology from linear to semidefinite programming. Even though the interior-point machinery carries over nicely from linear to semidefinite optimization, the computational overhead due to dense linear algebra operations makes it necessary to explore algorithmic alternatives to interior-point methods. The hyperplane rounding idea of Goemans and Williamson has turned out to be a strong theoretical tool in the approximation analysis of algorithms, opening up a new area of research in theoretical computer science. Finally, the new relaxations can also be used to solve problems to optimality. This requires algorithmic engineering to combine (nonlinear) bounding techniques with limited enumeration.

It is the purpose of the summer institute to focus on recent developments in this area. The following topics are of major interest to the ESI.

- Investigation of new relaxations for NP-hard problems,
- Algorithms for large scale semidefinite programs and related other conical relaxations of combinatorial optimization problems,
- Investigation of rounding heuristics, based on these relaxations,
- Investigation of theoretical error estimates of these relaxations,
- Exact solution methods, using semidefinite relaxations in combination with enumeration techniques

The ESI will combine tutorial lectures given by the invited speakers with student contributions and scientific discussions in small groups. It offers a unique opportunity for young scientists to acquaint themselves with state of the art methods in combinatorial optimization, to make some first contacts in the scientific community, and to share their experience with young colleagues from all over the world.

Invited Speakers

- Miguel Anjos (University of Waterloo, Canada)
- Etienne de Klerk (Tilburg University, The Netherlands)
- Christoph Helmberg (Technische Universitaet Chemnitz, Germany)
- Florian Jarre (Universität Düsseldorf, Germany)
- Veronica Piccialli (Università degli Studi di Roma Tor Vergata, Italy)

Conference Venue

The conference will be held at the Alpen-Adria-Universität Klagenfurt, Austria, which is located at the beautiful lake “Wörthersee”.

Committee

Members of the local organizing committee are Franz Rendl, Angelika Wiegele and Philipp Hungerländer (all of them belong to the Alpen-Adria-Universität Klagenfurt).

How to Participate

- Participation is limited to a group of about 20 doctoral or early post-doctoral students, who have reasonable familiarity with the field, and are authors or co-authors of at least one high-quality working paper (neither published nor submitted for publication) in the scope of the summer institute.
- Students interested in participating in ESI 2010 should send their application, consisting of their curriculum vitae and an unpublished paper in the scope of ESI 2010 to their national OR Society. (A list of the european OR societies can be found at http://www.euro-online.org/display.php?pageid=440& )
- The national OR Societies are entitled to nominate at least one participant (possibly up to three) to the ESI.
- The costs of the ESI are met by EURO and other organisations, excluding the paricipants’ travel expenses which are normally met by the corresponding national OR Society.
- In case, there are too many nominations, the final decision about participation will be made by the local organizing committee.

Deadlines

The deadline for application at the national OR Societies is March 15, 2010. The nominations from the national OR Societies will have to be forwarded to the chairman of the local committee, Franz Rendl (franz.rendl@uni-klu.ac.at), by March 31, 2010 the latest. A final decision about participation will be made beginning April 1, 2010.

Publication

It is planned to have a special issue of an optimization journal which will feature a selection of the papers submitted to the ESI. These will have to undergo the usual peer-reviewing process.

Further Information

For further information and subsequent updates please see also the webpage http://esi2010.uni-klu.ac.at, or alternatively, send your request by e-mail to franz.rendl@uni-klu.ac.at.


Ga terug naar het nieuwsoverzicht