Doctoral Schools
Scientific Organizers:
The lectures will be given by:
The school is organized with the support of the Marie Curie Research Training Network Algorithmic Discrete Optimization (ADONET). To register please visit the ROSS webpage
Prof. Michel Goemans, Massachusetts Institute of Technology, USA
Prof. Michel X. Goemans received his Ph.D. in 1990 from MIT, where he is now a Professor of Applied Mathematics. He has held a professorship at the Université Catholique de Louvain and an adjunct professorship at the University of Waterloo. His research interests are in mathematical programming and theoretical computer science, and especially in algorithmic, structural and polyhedral aspects of combinatorial optimization problems. His awards include the Fulkerson prize, twice the SIAM Optimization prize, the Tucker prize and a Sloan fellowship. He has been an invited speaker at many conferences, including the International Congress of Mathematicians in 1998. He has been on the program committee of several major theoretical computer science conferences, including as chair of the 2003 Symposium on Theory of Computing.
Due to the NP-hardness of many combinatorial optimization problems, there has been much interest in designing approximation algorithms --- polynomial-time algorithms delivering solutions with a guarantee of suboptimality. This is a very active area and there have been many developments in the last 15 years, both on the complexity side (limits to approximability) and on general techniques to design and analyze such algorithms.
In this series of lectures, I will discuss some recent approximation results, with an emphasis on the techniques used. Among several other topics, the lectures will cover the approximation of the sparsest cut problem through metric embeddings, the use of matroid intersection for bounded-degree spanning trees, the approximation of stochastic variants of combinatorial optimization problems and the latest progress on the maximum cut problem. The mini-course will be self-contained.
Technische Universiteit Eindhoven, The Netherlands
March 27 - 31, 2006
The admission fee for a minicourse is EUR 300 for university staff members and PhD students, and EUR 500 for people from industry. EIDMA and DIAMANT members receive a reduction of EUR 100 on these amounts. For undergraduate students special conditions apply. For the exact conditions please see the course registration form.
You can register by sending a completed registration form to Ms. Henny Houben at eidma@tue.nl. Deadline for registration is March 10, 2006. Please note that your registration is only official after our written confirmation of its receipt
The doctoral school will offer a comprehensive survey of the mathematical methods used in the theory of networks, as well as a set of more application-oriented lectures.
Topics covered will include Network flows, Network design, Approximation algorithms, and Game theoretical approaches. The application-oriented lectures will discuss Optical/multilayer networks, Wireless/ad-hoc networks, and peer-to-peer networks.
The speakers who have already confirmed their participation are:
The participation of the following speakers is yet to be confirmed:
More information and registration
Prof. Robin Thomas, Georgia Institute of Technology, USA
Robin Thomas received his doctorate from Charles University in Prague, Czech Republic, and is now a professor of mathematics at the Georgia Institute of Technology, with an adjunct appointment in industrial and systems engineering. His research interests center around the structure of graphs and applications to algorithms and graph coloring. Most recently he has worked on the Strong Perfect Graph Conjecture, Pfaffian orientations of graphs, and questions related to the Four-Color Theorem. He is currently writing a book on structural graph theory. In 1994 he received the D. Ray Fulkerson Prize (awarded jointly by the American Mathematical Society and the Mathematical Programming Society) and he is the editor of several journals.
Graph Structure Theory is concerned with establishing results that characterize various properties of graphs, and utilizes these theorems in the design of efficient algorithms and other applications. A typical example is the 2-paths theorem that relates two seemingly distant properties: the existence of two disjoint paths with specified ends and graph planarity.
The course will survey the major ingredients of the theory with special emphasis on graph minors: graph planarity, graphs on surfaces, representativity of surface embeddings, tree-width and related invariants, the excluded clique theorem and the k disjoint paths problem. We will present various applications, such as linkless embeddings of graphs, separators, Pfaffian orientations of graphs, Hadwiger's conjecture, the Four-Color theorem and its generalizations, and digraph minors. If time permits we will also discuss perfect graphs and the Strong Perfect Graph Conjecture.
Technische Universiteit Eindhoven, The Netherlands
June 6 - 10, 2005
The admission fee for this minicourse is EURO 700. However, our courses are free of charge for EIDMA members and for university students in general. Reductions or exemptions do apply to members of other academic insitiutes. For the exact conditions please see our minicourse registration form
You can register by sending a completed registration form to Ms. Henny Houben at eidma@tue.nl. Deadline for registration is May 29, 2005. Please note that your registration is only official after our written confirmation of its receipt.
Euler Institute for Discrete Mathematics and its Applications
Technische Universiteit Eindhoven
P.O. Box 513
5600 MB Eindhoven
The Netherlands
telephone: +31 (0)40 247 3121
telefax: +31 (0)40 243 5810
e-mail: eidma@tue.nl
WWW-page:
ww.win.tue.nl/math/eidma
This 2-day workshop gives an introduction to new functionality in Xpress-Mosel and Xpress-Optimizer. It is particularly aimed at researchers and other advanced users. The workshop will be preceded by a half-day crash course on Mosel for participants who are not familiar with this software or who only occasionally use Mosel and wish to refresh their knowledge.
The workshop is designed as a hands-on training course, participants are expected to bring their laptop computer. The course software will be provided.
The number of participants is limited to 20.
Registration deadline: 20 April, 2005
More information and registrationThe school offers introductions into the following four subjects of current interest. No special prior knowledge is expected.
Participants are expected to stay for the entire school.
Registrations should be emailed to adonet@informatik.uni-koeln.de.
We can offer accommodation in double rooms for the duration of the school (i.e. arrival on 5 Sep 2004, departure on 11 Sep 2004 or later) at a special rate of EUR 29.50 per person and night including breakfast on a first-come-first-served basis for at most 30 participants who register no later than 28 June 2004. If you are interested in this offer, please indicate so in your registration email and specify arrival and departure times. Notification will be sent out on 30 June 2004. All other participants will be asked to make their own accommodation arrangements. Travel, accommodation and living expenses must be paid by (the home institutions of) the participants. Due to ADONET sponsoring, there will be no fee for participation and course material.
The developments in the past have revealed the practical importance of developing algorithmic tools for tackling mixed integer optimization problems. Given our ability to solve linear optimization problems efficiently, one is inclined to think that a mixed integer program with both continuous and discrete variables is easier than a pure integer programming problem since integrality on the variables is required for a subset of the variables only. This however is not true at all. In fact, a second view towards a mixed integer program shows that the mixture of continuous and discrete components causes a significant increase in complexity with respect to geometric, algebraic, combinatorial and algorithmic properties.
In this light it is not too surprising that not only the derivation of cutting planes for a mixed integer program is more involved than in the pure integer setting, but also that there is no finite cutting plane algorithm known for general mixed integer programs, except for the special case when the support of the linear objective function vector is contained in the subset of the integer variables. This lecture is dedicated to the question to what extend some of the results about geometry, theory and algorithms in integer optimization can be generalized to the mixed integer scenario, i.e., an optimization problem described by linear equations and inequalities, a linear objective function and nonnegative variables where only some of the variables are required to attain an integer value. Specifically, we will treat the following topics:
If you have any suggestions, please contact webmaster @ads.tuwien.ac.at. Last modification: