TU BRAUNSCHWEIG
| Carl-Friedrich-Gauß-Fakultät | Informatik
Informatikzentrum

Seminar Algorithmik

Modulnr.INF-ALG-019
Veranst.Nr.INF-ALG-019
Studieng.Diplom Informatik, Master Informatik, Master Wirtschaftsinformatik, Bachelor Informations-Systemtechnik, Master Informations-Systemtechnik, Bachelor Elektrotechnik, Master Elektrotechnik, Bachelor Informatik
IBR Gruppe(n)ALG (Prof. Fekete)
ArtSeminar
Dozent
PhotoProf. Dr. Sándor P. Fekete
Abteilungsleiter
s.fekete[[at]]tu-bs.de
+49 531 3913111
Raum 335
Assistenten
PhotoDr. Christiane Schmidt
Ehemalige Wissenschaftliche Mitarbeiterin
cschmidt[[at]]ibr.cs.tu-bs.de
PhotoDr. Alexander Kröller
Ehemaliger Juniorprofessor
LP4
SWS0+2
Ort & Zeit

Die Vorbesprechung findet am 25.10.2010 um 15.00 Uhr in Raum 262A statt.

ACHTUNG NEU:
Die Abgabe der schriftlichen Ausarbeitung muss bis zum 03.01.2010 erfolgen.
In einer Blockveranstaltung am 14.01.2011 von 09:00 - 12:15 und am 17.01.2011 von 12:30 - 17:00 Uhr in Raum 262A werden die Vorträge gehalten.

Datum Zeit Thema Seminarist Betreuer
14.01.2010 09:00 Ein Push-Relabel Algorithmus für das Maximum-Flow-Problem Sebastian Saal Max Pagel
14.01.2010 10:00 Minimum Cost Flows Bennet Sartori Martin Lorek
14.01.2010 11:15 The Knapsack Problem Daniel Fricke Christiane Schmidt
17.01.2010 12:30 Bin-Packing Jan-Christoph Kalo Björn Hendriks
17.01.2010 13:30 Shortest Arborescences and Minimum Weight Arborescences Paul Wiemann Tom Kamphans
17.01.2010 15:00 What Cannot Be Computed Locally? Stephan Friedrichs Alexander Kröller
17.01.2010 16:00 Gappa: Gossip Based Mulit-channel Reprogramming for Sensor Networks Toni Günther Tom Kamphans
Scheinerwerb

Schriftliche Ausarbeitung und erfolgreicher Seminarvortrag. Die Note wird abhängig von der aktiven Teilnahme am Seminar sowie der Qualität des Vortrages und der Ausarbeitung bestimmt.

Vortrag: Ihr Vortrag sollte ca. 40 Minuten dauern. Das Medium ist frei, Sie können also Tafel, Overhead-Projektor, Beamer mit PowerPoint, Beamer mit PDF, oder was auch immer Sie sinnvoll finden, einsetzen. Natürlich sollten Sie bei exotischen Wünschen diese erstmal mit dem Betreuer klären, und unbedingt auch Programm-, Programmversions- und sonstige Kompatibilitätsfragen besprechen.

Ausarbeitung: Schreiben Sie eine Ausarbeitung, die Sie zwei Wochen vor dem Vortrag abgeben. Die Ausarbeitung soll ca. 5 Seiten lang sein. Generell interessiert uns aber, dass Sie da eine selbstverfasste Zusammenfassung eines selbst verstandenen Artikels abgeben. Mehr als zehn Seiten sollten es dennoch nicht werden, immerhin geht es hier um die Kunst des Zusammenfassens.

Inhalt

Das Seminar Algorithmik im Wintersemester 2010/2011 beschäftigt sich mit einer Reihe von aktuellen Artikeln sowie Ausschnitten aus Büchern. Schwerpunkt sind diesmal die Themen Netzwerkalgorithmen sowie verteilte Algorithmen. Die ersten 5 unten genannten Themen gehören zum Gebiet der Netzwerkalgorithmen und beruhen auf Kapitelausschnitten aus dem Buch Combinatorial Optimization von Bernhard Korte und Jens Vygen (Korte, B. and Vygen, J.: Combinatorial Optimization, Theory and Applications, Springer Verlag, 2002), Thema 5 beruht zudem auf einem Kapitelausschnitt aus dem Buch Combinatorial Optimization von Alexander Schrijver (Schrijver, A.: Combinatorial Optimization, Polyhedra and Efficiency, Volume B, Springer Verlag, 2003). Unten beschrieben sind die Originalauszüge der Autoren zu den eigenen Artikeln und Buchkapiteln, die jeweils auf englisch erschienen, aber von überschaubarer Länge sind.

Netzwerkalgorithmen

Thema 1: Ein Push-Relabel Algorithmus für das Maximum-Flow-Problem

The Maximum Flow Problem:
Instance: A network (G,u,s,t)
Task: Find an s-t-flow of maximum value.
By definition and Theorem 8.5, a function f:E(G)->R+ is a maximum s-t-flow if and only if the following three conditions hold:
- f(e) \leq u(e) for all e in E(G)
- \sum_{e \in \delta-(v)} f(e) = \sum_{e \in \delta+(v)} f(e) for all v \in V(G)\{s,t}
- There is no f-augmenting path.
The PUSH-RELABEL ALGORITHM starts with an f satisfying the first and third condition and maintains them throughout. Naturally it stops, when the second condition is satisfied as well.

Thema 2: Minimum Cost Flows

In this chapter we show how we can take edge costs into account. For example, in our application of the MAXIMUM FLOW PROBLEM to the JOB ASSIGNEMENT PROBLEM mentioned in the introduction of Chapter 8 one could introduce edge costs to model that the employees have different salaries; our goal ist to meet a deadline when all jobs must be finished at minimum cost. Of course, there are many more applications.
A second generalization, allowing several sources and sinks, is more due to technical reasons. We introduce the general problem and an important special case in Section 9.1. In Chpater 9.2 we prove optimality criteria that are basis of the minimum cost flow algorithms presented in Section 9.3. These use algorithms of Chapter 7 for finding a minimum mean cycle or a shortest path as a subroutine.

Thema 3: The Knapsack Problem

Applications arise whenever we want to select an optimum subset of bounded weight from a set of elements each of which has a weight and a profit. We start by considering the fractional version in Section 17.1, which turns out to be solvable in linear time. The integral knapsack problem is NP-hard as shown in Section 17.2, but a pseudopolynomial algorithm solves it optimally.

Thema 4: Bin-Packing

Suppose we have n objects, each of a given size, and some bins of equal capacity. We want to assign the objects to the bins, using as few bins as possible, Of course the total size of the objects assigned to one bin should not exceed its capacity. Without loss of generality, the capacity of the bins is 1.
There are not many combinatorial optimization problems whose practical relevance is more obvious.
In Section 18.1 we prove that the BIN-PACKING PROBLEM is strongly NP-hard and discuss some simple approximation algorithms. We shall see that no algorithm can achieve a performance ratio better than 3/2(unless P=NP). However, one can achieve an arbitrary good performance ratio asymptotically: in Sections 18.2 and 18.3 we describe a fully polynomial asymptotic approximation scheme.

Thema 5: Shortest Arborescences and Minimum Weight Arborescences

We next consider trees in directed graphs. We recall some terminology and facts. Let D=(V,A) be a digraph. A branching is a subset B of A suchthat B contains no undirected circuit and such that for each vertex v there is at most one arc in B entering v. A root of B is a vertex not entered by any arc in B. For any branching B, each weak component of (V,B) contains a unique root.
A branching B is called an arborescence if the digraph (V,V) is weakly connected; equivalently, if (V,V) is a rooted tree. So each arborescence B has a unique root r. We say that B is rooted at r, and we call B an r-arborescence. An r-arborescence can be characterized as a directed spanning tree B such that each vertex is reachable in B from r. A digraphD=(V,A)contains an r-arborescence if and only if each vertex of D is reachable from r.
Let be given a digraph D=(V,A), a vertex r, and a length function l:A->Q+. We consider the problem of finding the shortest (=minimum length) r-arborescence.

Minimum Weight Arborescence Problem:
Instance: A digraph G, weights c:E(G)->R
Task: Find a minimum weight spanning arborescence in G or decide that none exists.

Verteilte Algorithmen

Thema 6: What Can Be Computed Locally?

The purpose of this paper is a study of computation that can be done locally in a distributed network. By locally we mean within time (or distance) independent of the size of the network. We consider Locally Checkable Labeling (LCL) problems, where the legality of a labeling can be checked locally (e.g., coloring). Our results include the following:
  • There are non-trivial LCL problems that have local algorithms.
  • There is a variant of the dining philosophers problem which can be solved locally.
  • Randomization cannot make an LCL problem local; i.e., if a problem has a local randomized algorithm then it has a local deterministic algorithm.
  • It is undecidable, in general, whether a given LCL has a local algorithm.
  • However, it is decidable whether a given LCL has an algorithm that operates in a given time t.
  • Any LCL problem that has a local algorithm haa one which is order-invariant (the algorithm depends only on the order of the processor ids).

Thema 7: What Cannot Be Computed Locally!

We give time lower bounds for the distributed approxima- tion of minimum vertex cover (MVC) and related problems such as minimum dominating set (MDS). In k communi- cation rounds, MVC and MDS can only be approximated by factors \Omega(n1{c/k^2})and \Omega(\delta^{1/k}/k) for some constant c, where n and \delta denote the number of nodes and the largest degree in the graph. The number of rounds required in order to achieve a constant or even only a polylogarith- mic approximation ratio is at least \Omega(\sqrt(\frac{log n}{log log n}})) and \Omega(\frac{log\delta}{ log log \delta}). By a simple reduction, the latter lower bounds also hold for the construction of maximal matchings and maximal independent sets.

Thema 8: Gappa: Gossip Based Mulit-channel Reprogramming for Sensor Networks

Reprogramming the sensor networks in place is an important and challenging problem. One way suggested for reprogramming is with the help of an UAV (Unmanned Ariel Vehicle). To reprogram a sensor network with the help of an UAV, one can either communicate the entire new program to one (or a few) sensor in the field, or let the UAV communicate parts of the code to a subset of sensor nodes on multiple channels at once. In the latter approach, the nodes need to communicate with each other to receive the remaining parts of the program. In this paper, we propose a protocol for such gossip between nodes. To better utilize the multi-channel resources and reduce contention, our protocol provides a multi-channel sender selection algorithm. This algorithm attempts to ensure that in any neighborhood, at any time, there is at most one sensor transmitting on a given frequency. Moreover, our sender selection algorithm is greedy in that it tries to select the sender that is expected to have the most impact for each channel. Our protocol also conserves energy by putting the nodes that are unlikely to contribute or receive data shortly to sleep state. Through simulation, we show that our protocol is faster and more energy efficient than the existing reprogramming approaches that assume that the new program is initially located only on a small set of nodes.

aktualisiert am 10.01.2011, 18:24 von Dr. Christiane Schmidt
printemailtop