Technische Universität Braunschweig
  • Study & Teaching
    • Beginning your Studies
      • Prospective Students
      • Degree Programmes
      • Application
      • Fit4TU
    • During your Studies
      • Freshmen-Hub
      • Term Dates
      • Information for Freshman
      • Practical Information
      • Additional Qualifications
      • Financing and Costs
      • Special Circumstances
      • Campus life
    • At the End of your Studies
      • Discontinuation and Credentials Certification
      • After graduation
      • Alumni
    • For Teaching Staff
      • Strategy, Offers and Information
      • Learning Management System Stud.IP
      • Team Teaching and Media Education
    • Contact
      • Student Advice Centre
      • Academic Advice Service
      • Admissions Office
  • Research
    • Research Profile
      • Core Research Areas
      • Clusters of Excellence
      • Research Projects
      • Research Centres
    • Early Stage Researchers
      • Promotion of early career scientists
      • PhD-Students
      • Postdocs
      • Junior research group leaders
      • Junior Professorship and Tenure-Track
      • Habilitation
      • Service Offers for Scientists
    • Research Data & Transparency
      • Transparency in Research
      • Research Data
      • Open Access Strategy
      • Digital Research Announcement
    • Research Funding
      • Research funding
    • Contact
      • Research Services
      • Academy for Graduates
  • International
    • International Students
      • Why Braunschweig?
      • Degree seeking students
      • Exchange Studies
      • Doctorate (PhD)
      • Refugee Students
      • Welcome Programme
      • TU Braunschweig Summer School
    • Scientists
      • Mobile Researchers at the TU Braunschweig
      • Research Services and European Office
    • Language and intercultural competence training
      • Learning German
      • Intercultural Communication
    • International Profile
      • Internationalisation
      • International Cooperation
    • International House
      • Information for first semester students
      • Contact
      • News and Events
      • Advisory Services
      • Location
      • About us
  • TU Braunschweig
    • Our Profile
      • Aims & Values
      • Regulations and Guidelines
      • Alliances & Partners
      • Facts & Figures
      • Our History
    • Career
      • Working at TU Braunschweig
      • Vacancies
    • Economy & Business
      • Knowledge and Technology Transfer
      • Entrepreneurship
    • General Public
      • Access to the University Library
    • Media Services
      • Communications and Press Service
      • Communications and Press Service
      • Film and photo permits
      • Advices for scientists
      • Topics and stories
    • Contact
      • General Contact
      • Getting here
  • Organisation
    • Presidency & Administration
      • Presidency
      • Designated Offices
      • Administration
      • Committees
    • Faculties
      • Carl-Friedrich-Gauß-Fakultät
      • Faculty of Life Sciences
      • Architecture, Civil Engineering and Environmental Sciences
      • Faculty of Mechanical Engineering
      • Fakultät für Elektrotechnik, Informationstechnik, Physik
      • Faculty of Humanities and Studies in Education
    • Institutes
      • Institutes from A to Z
    • Facilities
      • University Library
      • Gauß-IT-Zentrum
      • International House
      • Sports Centre
      • Facilities from A to Z
    • Equal Opportunity Office
      • Equal Opportunity Office
      • Family
      • Diversity for Students
  • Search
  • Quicklinks
    • People Search
    • Webmail
    • Campus map
    • CloudStorage
    • Messenger
    • Cafeteria
    • Courses
    • Stud.IP
    • Library Catalogue
    • IT Self-Service
    • Information Portal (employees)
    • Link Collection
    • DE
    • EN
    • IBR Twitter
    • IBR YouTube
    • Facebook
    • Twitter
    • Instagram
    • YouTube
    • LinkedIn
Menu
  • Technische Universität Braunschweig
  • Organisation
  • Faculties
  • Carl-Friedrich-Gauß-Fakultät
  • Institutes
  • Institute of Operating Systems and Computer Networks
Logo IBR
IBR Login
  • Institute of Operating Systems and Computer Networks
    • News
    • About us
      • Whole Team
      • Directions
      • Floor Plan
      • Projects
      • Publications
      • Software
      • News Archive
    • Connected and Mobile Systems
      • Team
      • Courses
      • Theses
      • Projects
      • Publications
      • Software
      • Datasets
    • Distributed Systems
      • Team
      • Courses
      • Theses
      • Projects
      • Publications
      • Software
    • Algorithms
      • Team
      • Courses
      • Theses
      • Projects
      • Publications
    • Microprocessor Lab
    • Education
      • Summer 2023
      • Winter 2022/2023
      • Summer 2022
      • Theses
    • Services
      • Library
      • Mailinglists
      • Webmail
      • Knowledge Base
      • Wiki
      • Account Management
    • Spin-Offs
      • Docoloc
      • AIPARK
      • Confidential Technologies
    • Research Cooperations
      • IST.hub

Seminar Algorithmik

Semester
Winter 2010/2011
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
ProgrammesDiplom 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 GroupALG (Prof. Fekete)
TypeSeminar
Lecturer
Photo
Prof. Dr. Sándor P. Fekete
Abteilungsleiter
s.fekete[[at]]tu-bs.de
+49 531 3913111
Room 335
Assistants
Photo
Dr. Christiane Schmidt
Ehemalige Wissenschaftliche Mitarbeiterin
Photo
Dr. Alexander Kröller
Ehemaliger Juniorprofessor
Credits4
Hours0+2
Time & Place

Die Vorbesprechung findet am 25.10.2010 um 15.00 Uhr in Room 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 Room 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 *** Max Pagel
14.01.2010 10:00 Minimum Cost Flows *** Martin Lorek
14.01.2010 11:15 The Knapsack Problem *** Christiane Schmidt
17.01.2010 12:30 Bin-Packing *** Björn Hendriks
17.01.2010 13:30 Shortest Arborescences and Minimum Weight Arborescences *** Tom Kamphans
17.01.2010 15:00 What Cannot Be Computed Locally? *** Alexander Kröller
17.01.2010 16:00 Gappa: Gossip Based Mulit-channel Reprogramming for Sensor Networks *** Tom Kamphans
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.

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.

last changed 2018-06-13, 08:55 by Dr. Arne Schmidt

For All Visitors

Vacancies of TU Braunschweig
Career Service' Job Exchange 
Merchandising

For Students

Term Dates
Courses
Degree Programmes
Information for Freshman
TUCard

Internal Tools

Glossary (GER-EN)
Change your Personal Data

Contact

Technische Universität Braunschweig
Universitätsplatz 2
38106 Braunschweig

P. O. Box: 38092 Braunschweig
GERMANY

Phone: +49 (0) 531 391-0

Getting here

© Technische Universität Braunschweig
ImprintPrivacyAccessibility