Seminar Algorithmik
| Semester | Summer 2023Winter 2022/2023Summer 2022Winter 2021/2022Summer 2021Winter 2020/2021Summer 2020Winter 2019/2020Summer 2019Winter 2018/2019Summer 2018Winter 2017/2018Summer 2017Winter 2016/2017Summer 2016Winter 2015/2016Summer 2015Winter 2013/2014Summer 2013Winter 2012/2013Summer 2012Winter 2011/2012Summer 2011Winter 2009/2010Summer 2009Winter 2008/2009 | ||||||||||||||||||||||||||||||||||||||||
| Module # | INF-ALG-019 | ||||||||||||||||||||||||||||||||||||||||
| Event # | INF-ALG-019 | ||||||||||||||||||||||||||||||||||||||||
| Programmes | Diplom Informatik, Computer Science Master, Business Information Systems Master, Computer and Communication Systems Engineering Bachelor, Computer and Communication Systems Engineering Master, Electrical Engineering Bachelor, Electrical Engineering Master, Computer Science Bachelor | ||||||||||||||||||||||||||||||||||||||||
| IBR Group | ALG (Prof. Fekete) | ||||||||||||||||||||||||||||||||||||||||
| Type | Seminar | ||||||||||||||||||||||||||||||||||||||||
| Lecturer | |||||||||||||||||||||||||||||||||||||||||
| Assistants | Dr. Christiane Schmidt Ehemalige Wissenschaftliche Mitarbeiterin Dr. Alexander Kröller Ehemaliger Juniorprofessor | ||||||||||||||||||||||||||||||||||||||||
| Credits | 4 | ||||||||||||||||||||||||||||||||||||||||
| Hours | 0+2 | ||||||||||||||||||||||||||||||||||||||||
| Time & Place | Die Vorbesprechung findet am 25.10.2010 um 15.00 Uhr in Room 262A statt. ACHTUNG NEU:
| ||||||||||||||||||||||||||||||||||||||||
| Certificates | 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. | ||||||||||||||||||||||||||||||||||||||||
| Content | 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. | ||||||||||||||||||||||||||||||||||||||||
NetzwerkalgorithmenThema 1: Ein Push-Relabel Algorithmus für das Maximum-Flow-ProblemThe 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 FlowsIn 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 ProblemApplications 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-PackingSuppose 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 ArborescencesWe 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 AlgorithmenThema 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:
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 NetworksReprogramming 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. | |||||||||||||||||||||||||||||||||||||||||