Headline: teaching - colloquium CGC logo

Summer 2002 former semesters

Time: Mondays, 14:15 - 15:45
Location: IFW A32
(unless stated otherwise)

Organizers: CGC faculty at ETH Zurich
Contact: Emo Welzl


March 25, 2002, ETZ F76.1, (also TIK seminar; note location!)

Klaus Jansen
University of Kiel

Approximation Algorithms for General Packing Problems with Logarithmic
Potential Function


May 06, 2002, No talk, but note: 16.15, IFW A36, Informatik Kolloquium, Distinguished Lecture Series
Adi Shamir
Weizmann Institute, Israel

Broadcast encryption schemes


May 13, 2002
Jorgen Tind
University of Copenhagen

Convex Hull Computation and its Applications in Data Envelope Analysis


May 13, 2002, Note also the following lecture: 16.15 - 18.00, BB 001 at Zahnärztliches Institut, Plattenstr. 11
Martin Grötschel
TU Berlin and Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)

Was gibt es Neues in der Online-Optimierung?


Tuesday, May 21, 2002, Note the following lecture: 17.15 - 18.15, Mathematisches Kolloquium Zürich
Hörsaal 150, 1. Stock, Universität Zentrum, Karl-Schmid-Strasse 4, 8006 Zürich Kollegiengebäude 2 (Eingang Zoologisches Museum)
Martin Aigner
FU Berlin

Polyeder, Volumina und Primzahlen - eine Tour de Math


Tuesday, June 4, 2002, Note the following lecture: 17.15 - 18.15, Mathematisches Kolloquium Zürich
Hörsaal 150, 1. Stock, Universität Zentrum, Karl-Schmid-Strasse 4, 8006 Zürich Kollegiengebäude 2 (Eingang Zoologisches Museum)
Karl Sigmund
University of Vienna

John Nash und das Gleichgewicht: "Spieltheorie in Wirtschaft und Gesellschaft"


June 10, 2002
Jirí Matousek
Charles University, Prague

In praise of fractional Helly theorems


June 17, 2002
Friedhelm Meyer auf der Heide
Heinz Nixdorf Institute and Department of Mathematics and Computer Science
University of Paderborn

Data Management in Networks


Tuesday - Thursday, June 25 - June 27, 2002 , Note: Symposium on Applied Mathematics at the University of Zurich (Irchel Campus)


July 01, 2002
Ismael Regis de Farias, Jr.
CORE, Louvain-la-Neuve, Belgium

Branch-and-Cut for Combinatorial Optimization Problems without Auxiliary Binary Variables



Monday, March 25, 2002, 14:15 - 15:45, ETZ F76.1, (also TIK seminar; note location!)

Approximation Algorithms for General Packing Problems with Logarithmic
Potential Function

Klaus Jansen
University of Kiel

In this talk we present an approximation algorithm based on Lagrangian decomposition via a logarithmic potential reduction to solve a general packing or min-max resource sharing problem with M nonnegative convex constraints on a convex set B. We generalize a method by Grigoriadis and Khachiyan to the case with weak approximate block solvers (i.e. with only constant, logarithmic or even worse approximation ratios). We show that the algorithm needs at most calls to the block solver, a bound independent on the data and the approximation ratio of the block solver. For small approximation ratios the algorithm needs at most calls to the block solver. As an application we study the problem of minimizing the maximum edge congestion in a multicast communication network. Interestingly the block problem here is the classical minimum Steiner tree problem that can be solved only approximately. We show how to use approximation algorithms for the minimum Steiner tree problem to solve the edge congestion problem approximately. This is joint work with Hu Zhang, University of Kiel.


Monday, May 06, 2002, No talk, but note: 16.15, IFW A36, Informatik Kolloquium, Distinguished Lecture Series

Broadcast encryption schemes

Adi Shamir
Weizmann Institute, Israel

Broadcast encryption schemes enable a center to broadcast encrypted programs so that only a designated subset of users (which can change over time in an unpredictable way) can decrypt each program. The problem was first defined and studied by Fiat and Naor in 1993, and attracted a lot of practical and theoretical interest. In this self-contained talk I'll survey the field, describe a number of previous solutions, and introduce a new scheme which is exceptionally efficient: A broadcaster can address any subset of n users defined by any combination of k inclusion and exclusion conditions by initially giving each user slightly more than log(n) keys and then broadcasting a message of length k. The same keys can be used to encrypt an unlimited number of programs to dynamically changing subsets, there is no need to change them when users join or leave the system, and the scheme remains secure even if all the nonaddressed users form an adversarial coalition.


Monday, May 13, 2002, 14:15 - 15:45, IFW A32

Convex Hull Computation and its Applications in Data Envelope Analysis

Jorgen Tind
University of Copenhagen

The mathematical programming approach to efficiency evaluation, most notably Data Envelopment Analysis, has proved useful in numerous applications. Part of its success is due to the wide class of production structures that can be approximated using linear programming. The original model by Banker, Charnes and Cooper, the so-called VRS model makes a (minimal extrapolation) approximation of an arbitrary production possibility set that is convex and satisfies free disposability of inputs and outputs.

From a theoretical as well as an applied point of view, however, even the convexity assumption can be questioned.

Several attempts have been made to relax the convexity assumption. This presentation introduces a different modeling approach, the so-called convex pairs approach. It enables us to work with convexity around one or more observations without assuming convexity across all observations in input space, in output space or in the full production space.

Dual representations can be developed using blocking and anti-blocking theory from combinatorial optimization. They are useful for an efficient algorithmic implementation of the convex pairs approach. This involves the computation of the extreme points of a polytope given by its facets or, dually, the computation of the facets of a polytope defined by its extreme points.

In all cases, the resulting efficiency programs can be formulated and solved as disjunctive programming problems.

(joint work with Per J. Agrell, Peter Bogetoft and Michael Brock)


Monday, May 13, 2002, Note also the following lecture: 16.15 - 18.00, BB 001 at Zahnärztliches Institut, Plattenstr. 11

Was gibt es Neues in der Online-Optimierung?

Martin Grötschel
TU Berlin and Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)


Tuesday, May 21, 2002, Note the following lecture: 17.15 - 18.15, Mathematisches Kolloquium Zürich
Hörsaal 150, 1. Stock, Universität Zentrum, Karl-Schmid-Strasse 4, 8006 Zürich Kollegiengebäude 2 (Eingang Zoologisches Museum)

Polyeder, Volumina und Primzahlen - eine Tour de Math

Martin Aigner
FU Berlin

Jeder kennt das Volumen oder die Oberfläche eines Körpers im Raum. Aber was ist das Volumen wirklich? Wie lassen sich unsere intuitiven Begriffe Volumen und Oberfläche mathematisch beschreiben, und wie unterscheiden sie sich von anderen denkbaren Messungen? Interessanterweise führen diese Fragen zu einer der schönsten Formeln der gesamten Mathematik, der Eulerschen Polyeder-Formel.

Diese Formel gibt einen wunderbaren Zusammenhang zwischen den Anzahlen der Ecken, Kanten und Seiten eines Polyeders. Und sofort stellt sich die umgekehrte Frage: Angenommen wir haben diese Anzahlen vorgegeben, gibt es dann ein zugehöriges Polyeder? Dieses (im allgemeinen ungelöste) Problem leitet nun geradewegs zur Teilbarkeit von Zahlen und zu Primzahlen über. Auf unserer Tour de Math werden wir den Primzahlsatz besprechen und das vielleicht berühmteste offene Problem der Mathematik, die Riemannsche Vermutung.


Tuesday, June 4, 2002, Note the following lecture: 17.15 - 18.15, Mathematisches Kolloquium Zürich
Hörsaal 150, 1. Stock, Universität Zentrum, Karl-Schmid-Strasse 4, 8006 Zürich Kollegiengebäude 2 (Eingang Zoologisches Museum)

John Nash und das Gleichgewicht: "Spieltheorie in Wirtschaft und Gesellschaft"

Karl Sigmund
University of Vienna

Durch einen ungewöhnlichen Hollywoodfilm und einen weltweiten Bestseller wurde das Leben des John Nash auch einem grösseren Publikum nähergebracht. Nash revolutionierte zu Beginn der Fünfzigerjahre als junges Mathematikgenie die Grundlagen der Spieltheorie, einem wesentlichen Werkzeug der Sozial- und Wirtschaftswissenschaften. Das Konzept des Nash-Gleichgewichts ist wie kein anderes geeignet, um die Spannungen zwischen Eigennutz und Gemeinnutz zu analysieren und die oftmals paradoxen sozialen Ergebnisse individueller Entscheidungen zu verstehen.


Monday, June 10, 2002, 14:15 - 15:45, IFW A32

In praise of fractional Helly theorems

Jirí Matousek
Charles University, Prague

A famous theorem of Helly states that if any at most d+1 sets of a finite family of convex sets in Rd intersect, then all sets in the family intersect. Analogues of this statement for other kinds of sets (Helly-type theorems) have been investigated extensively. In many interesting cases, though, the Helly number is larger than ``expected'', or it is even infinite. For instance, for convex lattice sets in Zd, the Helly number is as large as 2d. The fractional Helly property, introduced by Katchalski and Liu, seems to behave much better, as we will illustrate. For example, lattice convex sets in Zd have fractional Helly number only d+1 (joint work with Imre Barany), and a bounded VC-dimension implies a bounded fractional Helly number. Fractional Helly theorems have further consequences, such as (p,q)-theorems and the existence of weak epsilon-nets, as follows from ideas of Alon and Kleitman.


Monday, June 17, 2002, 14:15 - 15:45, IFW A32

Data Management in Networks

Friedhelm Meyer auf der Heide
Heinz Nixdorf Institute and Department of Mathematics and Computer Science
University of Paderborn

This talk surveys strategies for distributing and accessing shared objects in large parallel and distributed systems. Examples for such objects are, e.g., global variables in a parallel program, pages or cach lines in a virtual shared memory system, or shared files in a distributed system, for example in a distributed data server. I focus on strategies for distributing, accessing, and (consistently) updating such objects, which are provably efficient with respect to various cost measures. First I will give some insight into methods to minimize contention at the memory modules, based on redundant hashing strategies. This is of interest for, e.g., the design of real time storage networks, as we develop within our PReSto-project in Paderborn. The main focus of this talk is on presenting strategies that are tailored to situations where the bandwidth of the network (rather than the contention) is the bottleneck, so the aim is to organise the shared objects in such a way that congestion is minimized. First I present schemes that are efficient w.r.t. information about read- and write-frequencies. The main part of the talk will deal with online, dynamic, redundant data management strategies that have good competitive ratio, i.e., that are efficient compared to an optimal dynamic offline strategy that is constructed using full knowledge about the dynamic access pattern. Especially the case of memory restrictions in the processors will be discussed.


Tuesday - Thursday, June 25 - June 27, 2002 , Note: Symposium on Applied Mathematics at the University of Zurich (Irchel Campus), IFW A32



Monday, July 01, 2002, 14:15 - 15:45, IFW A32

Branch-and-Cut for Combinatorial Optimization Problems without Auxiliary Binary Variables

Ismael Regis de Farias, Jr.
CORE, Louvain-la-Neuve, Belgium

Many optimization problems involve combinatorial constraints on continuous variables. An example of a combinatorial constraint is that at most k out of the n nonnegative variables (n>k) may be positive. Traditionally, such problems have been modeled as mixed-integer programs by introducing auxiliary binary variables and additional constraints. Because the number of variables and constraints becomes larger and the combinatorial structure is not used to advantage, these mixed-integer programming models may not be solved satisfactorily, except for small instances. In this talk I will present a branch-and-cut approach that considers the combinatorial constraints without the introduction of binary variables. I will review the development of this approach and show how strong constraints can be derived using ideas from polyhedral combinatorics.


Former semesters

Winter 2001/02 , Summer 2001 , Winter 2000/01 , Summer 2000 , Winter 1999/2000 , Summer 1999 , Winter 1998/99 , Summer 1998 , Winter 1997/98 , Summer 1997


Last modified on 2002-06-17 17:13:24 by Falk Tschirschnitz <tschirsc@inf.ethz.ch>      Copyright © 2000-2001 CGC
!!! Dieses Dokument stammt aus dem ETH Web-Archiv und wird nicht mehr gepflegt !!!
!!! This document is stored in the ETH Web archive and is no longer maintained !!!