 |
| Vortragender: | Ulrich Bauer |
| email: | baueru_at_in.tum.de |
| Studienfach: | Student Informatik, TUM |
| Vortragsthema: | Some Simple and Surprising Approximation Results |
| Folien: | Teaser |
| Inhalt: | Introduction into the topic Approximation Algorithms via examples: Vertex Cover, Set Cover, Steiner Tree, TSP, Multiway Cut, Minimum k-Cut |
|
 |
| Vortragender: | Stefan Kugele |
| email: | kugele_at_in.tum.de |
| Studienfach: | Student Informatik, TUM |
| Vortragsthema: | Complexity Classes for Optimization Problems |
| Folien: | Complexitytheory |
| Inhalt: | Algorithmic Complexity Classes: APX, PTAS, FPTAS, Gap-Technique and examples |
|
 |
| Vortragender: | Stefan Eckhardt |
| email: | eckhardt_at_in.tum.de |
| Studienfach: | Doktorand Informatik, TUM |
| Vortragsthema: | Shortest Common Superstring |
| Folien: | SCS |
| Inhalt: | Given a set of strings, the Shortest Common Superstring Problem is the Problem of
finding a string, called the superstring, such that all given strings are substrings of the superstring and such that the
superstring is shortest possible. The problem has its application first and foremost in computational biology, especially in the
analysis of the genome. Here the strings are a set of fragments of a gene and the task is to reconstruct the sequence of the original
gene. There is some evidence, that the shortest possible of all superstrings is very close to the original sequence.
In this talk only the combinatorial problem is covered. It is NP-hard but in APX. Some methods, based on Cycle Covers and
Maximum Traveling Salesperson, are introduced to approximate the problem. |
|
 |
| Vortragender: | Markus Herrmansdörfer |
| email: | herrmama_at_in.tum.de |
| Studienfach: | Student Informatik, TUM |
| Vortragsthema: | Introduction to Linear Programming and Duality |
| Folien: | IntrotoLP |
| Inhalt: | Constructing approximation algorithms with the aid of linear programming
(LP) is one of the most important and universal approaches in this
domain. This talk provides an introduction to linear programming by
first deriving the LP-duality theorem and by showing the connection
between min-max-relations and LP-duality. In the end, the most important
LP-based algorithm design techniques like rounding and primal-dual
schema are stated and compared to each other. |
|
 |
| Vortragender: | Alexander Offtermatt-Souza |
| email: | asouza_at_inf.ethz.ch |
| Studienfach: | Doktorand Informatik, ETHZ |
| Vortragsthema: | Knapsack and Bin Packing |
| Folien: | Knapsack |
| Inhalt: | The Knapsack Problem is one of the most fundamental problems in Computerscience. It has
various applications, is very well understood and therefore often is the starting point for the development of new algorithmic methods.
In this talk two versions of the problem are covered, the deterministic problem and a stochastic variation, where profits, weights and
the capacities are assumed to underly some propability distribution. An easy 1/2-Approximation based on a greedy strategy and an
approximation algorithm based on the technique of LP-Relaxation are presented. Then the algorithm of Nemhauser und Ullmann is
presented, which has a polynomial expected running time in the stochastic model.
|
|
 |
| Vortragender: | Martin Marciniszyn |
| email: | mmarcini_at_inf.ethz.ch |
| Studienfach: | Doktorand Informatik, ETHZ |
| Vortragsthema: | Maximum Satisfiability |
| Folien: | MaxSatSlides |
| Inhalt: | The Algorithm of Lieberherr and Specker is presented, which is a 3/4-approximation
for the MAX-SAT Problem. |
|
 |
| Vortragender: | Thomas Heynen |
| email: | thheynen_at_student.inf.ethz.ch |
| Studienfach: | Student Informatik, ETHZ |
| Vortragsthema: | Variations of Maximum Satisfiability and Further Rounding Techniques |
| Folien: | MAXSAT/Pipage |
| Inhalt: | Two rounding techniques especially designed to tackle problems with
Cardinality Constraints (CC). These techniques enable the rounding of
fractional solutions (of an LP) to Max SAT with CC, while maintaining the
constraints |
|
 |
| Vortragende: | Dinara Barshevich |
| email: | dinara200384_at_mail.ru |
| Studienfach: | Student, St. Petersburg |
| Vortragsthema: | Scheduling and Linear Programming |
| Folien: | Scheduling |
| Inhalt: | The presentation considers two principally different approximation
approaches to scheduling problem. The first one is revealed in a
constant-factor algorithm for the common case dealing with LP-technique,
namely LP-rounding combined with parametric pruning.
The other presents a PTAS for the restricted version of scheduling problem
using bin packing reduction and dynamic programming. |
|
 |
| Vortragender: | Manuel Huber |
| email: | manhuber@inf.ethz.ch |
| Studienfach: | Doktorand Informatik, ETHZ |
| Vortragsthema: | Introduction into Semidefinite Programming |
| Folien: | IntrotoSDP |
| Inhalt: | The technique of semidefinite programming (SDP) is introduced. Approximation algorithms for the
problems MAX-CUT, MAX-BISECTION and MAX-2SAT based on SDP are presented. Finally, LP is
shown to be a special case of SDP. |
|
 |
| Vortragender: | Dieter Mitsche |
| email: | dmitsche@inf.ethz.ch |
| Studienfach: | Doktorand, ETHZ |
| Vortragsthema: | Some Applications of Semidefinite Programming |
| Folien: | ApplicationsofSDP |
| Inhalt: | In this talk two recent papers dealing with applications of semidefinite
programming (SDP) are presented. The first one (by A. Blum, G. Konjevod,
R. Ravi and S. Vempala) shows how
SDP can be used to obtain approximation guarantees for the minimum
bandwidth problem which is known to be NP-hard. The second one (by U.
Feige and J. Kilian) explains (among
other things) how SDP can be used to find a mimimum bisection in
semirandom graphs. |
|
 |
| Vortragender: | Andreas Weissl |
| email: | aweissl_at_inf.ethz.ch |
| Studienfach: | Doktorand Informatik, ETHZ |
| Vortragsthema: | Multi Commodity Flow |
| Folien: | Part 1/Part 2 |
| Inhalt: | In the first part of the talk a detailed description how to apply the
primal-dual schema to design an approximation algorithm for the
multicommodity flow / minimum multicut problem in trees. Additionally a
short outlook how to design an approximation algorithm for minimum
multicut in general graphs will be given.
Second part of the talk introduces flows over time and techniques for
solving such problems. How to apply these methods to derive an FPTAS for
quickest multicommodity flow, are presented as an outlook. |
|
 |
| Vortragender: | Jan Remy |
| email: | jremy_at_inf.ethz.ch |
| Studienfach: | Doktorand Informatik, ETHZ |
| Vortragsthema: | Arora |
| Folien: | Arora |
| Inhalt: | The PTAS for the geometric version of the Travelling Salesperson Problem due to Arora
is presented. |
|
 |
| Vortragender: | Justus Schwartz |
| email: | jschwart_at_inf.ethz.ch |
| Studienfach: | Doktorand, ETHZ |
| Vortragsthema: | Counting Problems |
| Folien: | Counting |
| Inhalt: | Counting the number of solutions of a Problem is fundamental. Randomized Approximation
Schemes, Fully Polynomial Randomized Approximation Schemes, Uniform Sampling by rapidly mixing Markov Chains and as an
application the Zero-One-Knapsack Problem are covered in this talk. |
|
