printlogo
ETH Zuerich - Homepage
 
print
  

Seminar Combinatorial Optimization and Applications

In this seminar we will discuss selected topics from combinatorial optimization in the widest sense. Where applicable, modeling techniques, algorithms and performance guarantees with importance for applications, in particular in (systems) biology will be discussed.

This seminar has two goals: On the one hand we intend to present an overview of various topics in combinatorial optimization that are not covered in depth in the usual lectures. Furthermore, scientific skills, like reading and understanding an original research article, presenting
the main concepts and ideas to an audience with similar knowledge level, will be trained.

Organization

In the first class we will present the available topics, and assign them, usually to groups of 2, if necessary 3, students per topic. There will be no class in the second week, to allow the first presenters enough time for preparation.

Each topic will be presented in a blackboard/beamer presentation to the other participants, with about 20 minutes per speaker. A group presentation should take care to distribute material fairly among the participants. Regular attendance by all participants is expected and a criterion for obtaining the Testat.

Dates and Topics

Seminar time: Wednesday, 13-15 in Room HG E 33.3.

The articles listed on the topics page will be assigned on Feb 22.

22.2.2012 Introduction and Topic Assignment  
29.2.2012 No class -- preparation time  
7.3.2012 1/1: Optimal Packing and covering in the plane are NP-complete Serrano Zanetti, Mikelson
  CANCELLED: 1/2: Approximation schemes for convering and packing problems in image processing and VLSI Derendinger
14.3.2012 2/1: Polynomial-time approximation scheme for base station positioning in UMTS networks Gassner, Kappeler
  2/2: Hyperbolic set covering problems with competing ground-set elements Hertz, Sproelt
21.3.2012 3/1: Complexity of combinatorial optimization problems on d-dimensional boxes Ebbe, Deprez, Gyr
28.3.2012 4/1: College admissions and the stability of marriage Enz, Fricker
  4/2: Stable marriage with incomplete Lists and Ties Ernest, Lengacher
4.4.2012 6/1: Approximability results for stable marriage problems with ties Hüni, Pfister
  6/2: Simpler Approximation Algorithms for the stable marriage problem Puccio, Tschudi
11.4.2012 (Easter break)

 
18.4.2012 5/1: Path, trees and flowers Hänggli, Süess, Vogelsang
25.4.2012 RESCHEDULED TO THE FOLLOWING WEEK
7/1: A total-value greedy heuristic for the integer knapsack problem
 
2.5.2012 STARTING AT 13:00
7/1: A total-value greedy heuristic for the integer knapsack problem

RESCHEDULED TO THE FOLLOWING WEEK
9/1a and 9/1b: Linear Diophantine Systems
Link, Schwarz


Ghilmetti, Bader, Grüning
9.5.2012 9/1a and 9/1b: Linear Diophantine Systems

10/1: Testing for the Consecutive Ones Property
Ghilmetti, Bader, Grüning

Keusch, Wehner
  RESCHEDULED TO THE FOLLOWING WEEK
10/2: Minimal conflicting sets for the Consecutive Ones Property

Manoli, Bernhard
16.5.2012 10/2: Minimal conflicting sets for the Consecutive Ones Property

RESCHEDULED TO MAY 30:
11/1: Complexity of dualization of monotone disjunctive normal forms
Manoli, Bernhard

Klimkewitz, Meier, Mülle-Lennert
23.5.2012 12/1: Structure theorem for the Consecutive 1's Property De la Cruz Mengual, Mihovci
  Overview of Complexity of Packing Problems Ebbe
  12/2: Systematic Approach to MDD-Based Constraint Programming Ermatinger
30.5.2012 11/1: Complexity of dualization of monotone disjunctive normal forms Klimkewitz, Meier, Müller-Lennert
     
 

Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne graphische Elemente dargestellt. Die Funktionalität der Website ist aber trotzdem gewährleistet. Wenn Sie diese Website regelmässig benutzen, empfehlen wir Ihnen, auf Ihrem Computer einen aktuellen Browser zu installieren. Weitere Informationen finden Sie auf
folgender Seite.

Important Note:
The content in this site is accessible to any browser or Internet device, however, some graphics will display correctly only in the newer versions of Netscape. To get the most out of our site we suggest you upgrade to a newer browser.
More information

© 2013 Mathematics Department | Imprint | Disclaimer | 16 May 2012
top