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 KielApproximation Algorithms for General Packing Problems with Logarithmic
Potential Function
Adi Shamir
Weizmann Institute, Israel
Jorgen Tind
University of CopenhagenConvex Hull Computation and its Applications in Data Envelope Analysis
Martin Grötschel
TU Berlin and Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)
Martin Aigner
FU Berlin
Karl Sigmund
University of ViennaJohn Nash und das Gleichgewicht: "Spieltheorie in Wirtschaft und Gesellschaft"
Jirí Matousek
Charles University, Prague
Friedhelm Meyer auf der Heide
Heinz Nixdorf Institute and Department of Mathematics and Computer Science
University of Paderborn
Ismael Regis de Farias, Jr.
CORE, Louvain-la-Neuve, BelgiumBranch-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!)
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
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
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)
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
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)
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
A famous theorem of Helly states that if any at most d+1 sets of a finite family of convex sets in R^{d} 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 Z^{d}, the Helly number is as large as 2^{d}. The fractional Helly property, introduced by Katchalski and Liu, seems to behave much better, as we will illustrate. For example, lattice convex sets in Z^{d} 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
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.
Monday, July 01, 2002, 14:15 - 15:45, IFW A32
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.
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 |