Informella doktorandseminarier i teoretisk datalogi / Informal PhD Student Seminars in Theoretical Computer Science

The information below about the informal PhD student seminars in Theoretical Computer Science is mostly in Swedish, but seminars can also be (and are) presented in English. If you want to attend a seminar and do not understand Swedish, we will try to switch to English (if possible, we would appreciate forward notice of this to Björn Terelius). See also the information about the official seminars of the Theoretical Computer Science Group.

Teorigruppens doktorandseminarier är tänkta att vara informella och avspända utan de officiella seminariernas krav på "ytfinish". Seminarierna kan handla om färdiga forskningsresultat (egna eller från inlästa artiklar) eller om pågående arbete. Målgruppen är främst doktorander, men alla är välkomna och det finns en sändlista för seminarierna som man kan anmäla sig till om man är intresserad (kontakta Björn Terelius i sådana fall).

Mer information om upplägg och praktiska detaljer finns på en särskild sida. Det finns också en sida med tidigare seminarier.

Se även sidan för teorigruppens officiella seminarier.

Kommande doktorandseminarier vårterminen 2010 / Upcoming Seminars Spring 2010

• March 1 2010 13:15 1537
  Spotify's music streaming protocol
  (Gunnar Kreitz, KTH CSC)

  Spotify is a music streaming service offering a large library of licensed music for immediate playback. Streaming is done from a server-assisted peer-to-peer network, where our servers help guarantee availability and keep latency down, while the p2p network helps by offloading our servers.

  I will give an overview of, and describe some details of, the Spotify music streaming protocol. This seminar will likely be a bit more practical than most seminars in this series.

• Tuesday February 16, 10:30-12:00, room 4523:
  Approximating Max-Min and Min-Max Allocation Problems
  (Ola Svensson, KTH CSC)

  I will survey some of the recent results regarding the problem "Max-Min fair allocation" of allocating n resources to m players so as to maximize the happiness of the least happy player. We will analyze a strong linear programming formulation (known as Configuration LP) for this problem and show that it has integrality gap of at most 1/5.

  As the considered problem and the classic scheduling problem of minimizing the maximum load have a similar structure --- only the objective functions differ --- this gives hope that we can use a similar approach for the scheduling problem. I have some encouraging preliminary results in this direction but the main problems (that we hopefully can resolve together) are still open.

  References: The results I planned to cover are in the following articles:
  http://portal.acm.org/citation.cfm?id=1132522
  http://www.wisdom.weizmann.ac.il/~feige/mypapers/santaclaus1.pdf