Call for Participation:
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 EURO Summer Institute (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 to
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 at 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
.
click here to
print this text
|