Uni-Logo
Algorithms and Complexity
 

Proseminar / Seminar
"Algorithmen für adaptive Web-Strukturen"
Wintersemester 2007/08
Prof. Dr. Susanne Albers
Tobias Jacobs


Seminar


Zeit und Ort: Mittwochs, 14.15-15.45 Uhr, SR 01-018, Geb. 101
Die erste Seminarsitzung (Vorbesprechung und Themenvergabe) findet statt am Mi, 24. Oktober 2007.

Die Teilnahme an dieser Veranstaltung kann wahlweise entweder als Proseminar oder als Seminar angerechnet werden.

Die Anmeldung wird über HIS-LSF durchgeführt. Die Anzahl der Teilnehmer ist auf 14 begrenzt. Anmeldeschluss ist der 15. September 2007.

Bei Anregungen und Fragen zum Seminar wenden Sie sich bitte an Tobias Jacobs.

Aktuelles


28. Januar 2008
Die letzten beiden Seminarsitzungen fallen aus, d.h. die letzte Sitzung wird am 30. Januar 2008 stattfinden.

25. Oktober 2007
Alle Seminarteilnehmer sollten unbedingt daran denken, dass sie sich für die entsprechende Teilprüfung anmelden müssen.

19. Oktober 2007
Die Seminarthemen stehen fest.

Inhalt der Veranstaltung


Web-Directories stellen große Mengen an Informationen übersichtlich und strukturiert dar. Jede einzelne Information soll mit möglichst geringem Aufwand vom Benutzer gefunden werden können. Die Interessen der Benutzer sind jedoch stark korreliert: Typischerweise beziehen sich 80% aller Anfragen auf nur 20% aller Informationsangebote.
Seit einigen Jahren werden daher vermehrt Ansätze verfolgt, populäre Informationen schneller zugänglich zu machen. Hierfür bieten sich besonders nicht-destruktive Verfahren an, bei denen die ursprüngliche Web-Struktur erhalten bleibt. Eine interessante Möglichkeit hierfür bietet dabei das automatische Einfügen zusätzlicher Hyperlinks, sogenannter Hotlinks.

Im Mittelpunkt des Seminars stehen die aus dieser Motivation hervorgehenden algorithmischen Optimierungsprobleme. Es wird ein formales Modell für Web-Strukturen eingeführt und Algorithmen für verschiedene Szenarien entworden und analysiert.

Voraussetzungen

  • Grundkenntnisse in Algorithmen und Datenstrukturen (Informatik II)

  • Englischkenntnisse zur Aneignung der ausschl. englischsprachigen Literatur

Anforderungen

  • Anwesenheit und Mitarbeit

  • Gestaltung einer Seminarsitzung (Vortrag)

  • Schriftl. Ausarbeitung in Form eines Hand-Out

Themen

TerminThemaReferent
24. Oktober 2007Vorbesprechung und Themenvergabe
31. Oktober 2007Grundlegendes: Graphentheorie und Konzepte adaptiver Websites Manuel Braun
07. November 2007Web-Strukturen und Kodierungstheorie Rabie Hammoud
14. November 2007Generierung von Indexpages Guido Solbach
21. November 2007Optimale Platzierung von Web Proxies und Bookmarks Christoph Birkenbihl
28. November 2007Hotlinks und die Entropieschranke Philippe Hagedorn
05. Dezember 2007Hotlink Assignment: der h/ph-Algorithmus Martin Schilgen
12. Dezember 2007Anwendung: Asymmetrische Kommunikationsprotokolle Michael Leukert
19. Dezember 2007Hotlink Assignment auf Blätter beschränkt Sebastian Schefczyk
09. Januar 2008Komplexitätsklasse von Bookmark und Hotlink Assignment Benjamin Udiljak
16. Januar 2008Der Greedy-Algorithmus im Clairvoyant User Modell Sebastian Schmelzer
23. Januar 2008Der Greedy-Algorithmus im Greedy User Modell Johannes Wörner
30. Januar 2008Optimales Hotlink Assignment Cornelius Amzar
06. Februar 2008 fällt aus!
13. Februar 2008 fällt aus!

Literatur

  • M. Perkowitz and O. Etzioni. Adaptive Web Sites: an AI Challenge. In Proceedings of IJCAI ,1997.

  • M. Perkowitz and O. Etzioni. Adaptive Sites: Automatically Learning from User Access Patterns. University of Washington Dept. of Computer Science Tech Report.

  • M. Perkowitz and O. Etzioni. Adaptive Web Sites: Automatically Synthesizing Web Pages. In Proceedings of AAAI, 1998.

  • M. Perkowitz, and O. Etzioni. Towards Adaptive Web Sites: Conceptual Framework and Case Study. In Artificial Intelligence Journal, 2000.

  • P. Bose, J. Czyzowicz, L. Gasienicz, E. Kranakis, D. Krizanc, A. Pelc, M. Vargas Martin. Strategies for hotlink assignments. In Proceedings of 11th International Symposium on Algorithms and Computation (ISAAC), 2000.

  • P. Bose, D. Krizanc, S. Langerman, and P. Morin. Asymmetric communication protocols via hotlink assignments. In Proceeding of the 9th Colloquium on Structural Information and Communication Complexity (SIROCCO), 2002.

  • A. Pessoa, E. Laber, C. de Souza. Efficient algorithms for the hotlink assignment problem: The worst case search. In Proceedings of the 15th International Symposium on Algorithms and Computation (ISAAC), 2004.

  • R. Matichin, D. Peleg. Approximation algorithm for hotlink assignments in web directories. In Proceedings of 8th the Workshop of Algorithm Theory (WADS), 2003.

  • R. Matichin and D. Peleg. Approximation algorithm for hotlink assignment in the greedy model. In Proceedings of the 11th Colloquium on Structural Information and Communication Complexity (SIROCCO), Bratislava, Slovakia, June 2004.

  • Karim Douïeb, Stefan Langerman. Dynamic Hotlinks. In Proceedings of 9th International Workshop on Algorithms and Data Structures (WADS), 2005.

  • K. Douïeb, S. Langerman. Near-entropy hotlink assignments. In Proceedings of the 14th Annual European Symposium on Algorithms (ESA), 2006.

  • J. Czyzowicz, E. Kranakis, D. Krizanc, A. Pelc, M. Vargas Martin. Optimal Assignment of Bookmarks to Web Pages. Ars Combinatoria, January 2007.

  • Tobias Jacobs. Constant Factor Approximations for the Hotlink Assignment Problem. Proceedings of the 10th Workshop on Algorithms and Data Structures (WADS'07) , Halifax, 2007.