Von Worst-Case bis Average-Case Effizienz - Approximation von kombinatorischen Optimierungsproblemen
| Talking persons: |
| Dipl.-Inf. Kai Plociennik |
| Abstract: |
| Fragt man nach "guten" Approximationsalgorithmen, d.h. solchen, die eine gewisse akzeptable Güte der berechneten Lösungen garantieren, dann muss man immer auch festlegen, wie "schnell" ein solcher Algorithmus sein soll. Für verschiedene Effizienzbegriffe - von Worst-Case bis Average-Case Effizienz - lassen sich kombinatorische Optimierungsprobleme mehr oder weniger gut approximieren. 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: |
| Tuesday 9th November 2010, 3.30 pm - 4.15 pm, room 1/B006 |
