Approximation von kombinatorischen Optimierungsproblemen (Dissertationsverteidigung)
| Talking persons: |
| Dipl.-Inf. Kai Plociennik |
| Abstract: |
| Kai Plociennik verteidigt seine Dissertation mit dem Titel "From Worst-Case to Average-Case Efficiency - Approximating Combinatorial Optimization Problems". Für verschiedene Effizienzbegriffe - von Worst-Case bis Average-Case Effizienz - lassen sich kombinatorische Optimierungsprobleme mehr oder weniger gut approximieren. In seiner Dissertation hat Kai Plociennik die Approximierbarkeit verschiedener Optimierungsprobleme für unterschiedliche Effizienzbegriffe untersucht. Der Vortrag erklärt beispielhaft am Problem INDEPENDENT SET, wie sich verschiedene Relaxationen der Forderung nach Worst-Case Effizienz auf die Approximierbarkeit eines Problems auswirken können. |
| Times: |
| Thursday 27th January 2011, 10.00 am - 11.30 am, room 1/305 |
