2017S, VU, 2.0h, 3.0EC, wird geblockt abgehalten

## Merkmale

• Semesterwochenstunden: 2.0
• ECTS: 3.0
• Typ: VU Vorlesung mit Übung

to be informed

## Inhalt der Lehrveranstaltung

We explore a two-dimensional  "world" which has one axis for algorithmic methods and a second axis for models of computation. This world is explored by considering canonic problems such as maximum matching, minimum vertex cover, maximal independent set, and packing and covering. The axis of algorithmic methods consists of greedy selection, augmenting paths, primal-dual, and multiplicative weights. The models of computation are: the standard sequential model, distributed algorithms (LOCAL and CONGEST models), sublinear algorithms, online algorithms, and online learning.
Each model of computation is characterized by a dierent constraint that limits the algorithm designer. For example: in online algorithms, irrevocable decisions must be made before the whole input is revealed; in sublinear algorithms, decisions must be made based on seeing only a small fraction of the input; in distributed algorithms, decisions must be made based only on local information.
Overcoming these challenges often requires one to resort to approximate solutions. For example, instead of computing a maximum matching, we are satis ed with a matching, the cardinality of which at least (1 - ¿) times the maximum cardinality matching. Randomization is often employed to cope with partial information.

## It will be held by Guy Even, Tel-Aviv University.

The course will be held as blocked course.

## LVA Termine

TagZeitDatumOrtBeschreibung
Mo.13:00 - 16:0020.03.2017 Favoritenstraße 9-11, staircase 1, 4th floor, room: 183/2Algorithm Design in Different Models of Computation
Di.11:00 - 14:0021.03.2017 Favoritenstraße 9-11, staircase 1, 4th floor, room: 183/2Algorithm Design in Different Models of Computation
Mi.13:00 - 16:0022.03.2017 Favoritenstraße 9-11, Ground floor, Room: von NeumannAlgorithm Design in Different Models of Computation
Do.11:00 - 14:0023.03.2017 Favoritenstraße 9-11, Ground floor, Room: von NeumannAlgorithm Design in Different Models of Computation
Fr.13:00 - 16:0024.03.2017 Favoritenstraße 9-11, Ground floor, Room: von NeumannAlgorithm Design in Different Models of Computation
Di.13:00 - 16:0002.05.2017 Favoritenstraße 9-11, staircase 1, 4th floor, room: 183/2Algorithm Design in Different Models of Computation
Mi.13:00 - 15:0003.05.2017 Favoritenstraße 9-11, Ground floor, Room: von NeumannAlgorithm Design in Different Models of Computation
Do.13:00 - 16:0004.05.2017 Favoritenstraße 9-11, Ground floor, Room: von NeumannAlgorithm Design in Different Models of Computation
Fr.13:00 - 16:0005.05.2017 Favoritenstraße 9-11, Ground floor, Room: von NeumannAlgorithm Design in Different Models of Computation
LVA wird geblockt abgehalten

## LVA-Anmeldung

Von Bis Abmeldung bis
16.02.2017 00:00 20.03.2017 23:59

Anmeldemodalitäten:

## Curricula

StudienkennzahlSemesterAnm.Bed.Info
PhD Vienna PhD School of Informatics

## Literatur

Es wird kein Skriptum zur Lehrveranstaltung angeboten.

## Weitere Informationen

• Anwesenheitspflicht!

Englisch