English English

Termine

Art
Termin / Ort
Beginn
Veranstalter
S2
Di 14:00h - 15:30h / Seminarraum Lehrstuhl I
19.April
Vöcking, Newman, Röglin

 

Inhalt

Die Vorträge werden sich mit aktuellen Themen aus dem Bereich der kombinatorischen Optimierung beschäftigen. Geplante Themen sind beispielsweise Entwurf und Analyse von Approximationsalgorithmen und probabilistische Analysen von Algorithmen.

Voraussetzungen

  • Teilnahme an der Vorlesung Effiziente Algorithmen
  • Vorträge in Englisch sind erwünscht, jedoch nicht zwingend notwendig

Einführung in LaTeX

Die Folien des Vortrages und die Latex-Quellen findet ihr hier.

Präsentation der Vortragszusammenfassungen

Die kurzen Präsentationen eurer Vortragszusammenfassungen finden am Dienstag, den 19. April um 14.00 Uhr in Raum 5056 statt.

Vorträge

Termin
Thema
Vortragende
26. April Semi-Random Graph Problems

Coloring Random and Semi-Random k-Colorable Graphs
Journal of Algorithms, 19, 204-234, 1995
Avril Blum, Joel Spencer

Heuristics for Semirandom Graph Problems
Journal of Computer and System Sciences, 63, 639-671, 2001
Uriel Feige, Joe Kilian

Christoph Briem,
Jacob Spönemann
3. Mai Random Knapsack in Expected Polynomial Time

Random Knapsack in Expected Polynomial Time
Journal of Computer and System Sciences, 69, 306-329, 2004
Rene Beier, Berthold Vöcking

Silke Haferkamp,
Yi Yang
10. Mai Multi-Level Feedback Algorithm

Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm
FOCS 2003 (vollständige Version ist als Forschungsbericht des Max-Planck-Institutes erschienen)
Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Guido Schäfer, Tjark Vredeveld

Andre Brosig,
Sarah Mennicken
31. Mai Integral and Fractional Cycle Packing

Packing directed circuits fractionally
Combinatorica 15, 281-288, 1995
Paul Seymour

Approximation algorithms for cycle packing problems
SODA 2005
Michael Krivelevich, Zeev Nutov, Raphael Yuster

Jue Huang,
Jin Sun
14. Juni Randomized Metarounding

Randomized Metarounding
Random Structures and Algorithms, 20(3), 343-352, 2002
Robert Carr, Santosh Vempala

Daniel Herding,
Jan Dominik Rose
21. Juni Quadratic Programs

Approximating the cut-norm via Grothendieck's inequality
STOC 2004
Noga Alon, Assaf Naor

Maximizing quadratic programs: extending Grothendieck's inequality
FOCS 2004
Moses Charikar, Anthony Wirth

Quadratic forms on graphs
STOC 2005
Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor

Leonhard Lichtschlag,
Martin Sundermeyer
28. Juni k-Cuts

Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
Journal of Computer and System Sciences, 68, 442-472, 2004
Michel Goemans, David Williamson

On approximate graph colouring and MAX-k-CUT algorithms based on the Theta-function
Journal of Combinatorial Optimization, 8, 267-294, 2004
Etienne de Klerk, Dmitrii Pasechnik, Joost Warners

Improved approximation algorithms for MAX-k-CUT and MAX BISECTION
Algorithmica, 18(1), 1997
Alan Frieze, Mark Jerrum

Rifat Kilic,
Osmond Sanjaya Tedjasukmana
5. Juli Stochastic Load Balancing and Related Problems

Allocating Bandwidth for Bursty Connections
SIAM Journal on Computing, 30, 191-217, 2000
Jon Kleinberg, Yuval Rabani, Eva Tardos

Stochastic Load Balancing and Related Problems
FOCS 1999
Ashish Goel, Piotr Indyk

Adam Malik,
Mark Sillner
12. Juli Stochastic Knapsack

Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
FOCS 2004
Brian Dean, Michel Goemans, Jan Vondrak

Adaptivity and Approximation for Stochastic Packing Problems
SODA 2005
Brian Dean, Michel Goemans, Jan Vondrak

Thomas Wright
19. Juli An Approximation Scheme for Stochastic Linear Programming and its Application to Stochastic Integer Programs

An Approximation Scheme for Stochastic Linear Programming and its Application to Stochastic Integer Programs
FOCS 2004
David Shmoys, Chaitanya Swamy

Changhong Huang,
Xiaoqun Huang

 

Kontakt

  • Alantha Newman: alantha (at) cs.rwth-aachen.de
  • Heiko Röglin: roeglin (at) cs.rwth-aachen.de