DD3013 Summan av kvadrater och heltalsprogrammeringslättnader 6,0 hp

Sum of Squares and Integer Programming Relaxations

  • Utbildningsnivå

    Forskarnivå
  • Huvudområde

  • Betygsskala

    P, F

Det finns inget planerat kurstillfälle.

Lärandemål

Efter godkänd kurs ska studenterna kunna

  • läsa konferensartiklar inom kursens område,
  • redogöra för linjära och positivt semidefinita relaxeringar av heltalsprogram och hur dessa kan användas i approximationsalgoritmer,
  • visa undre gränser för kvadratsummesystemet och redogöra för metodens begränsningar.

Kursens huvudsakliga innehåll

Hierarkier av heltalsprogrammeringsrelaxeringar.

Kvadratsummesystemet.

Algoritmer som använder sådana relaxeringar.

Undre gränser för kvadratsummor.

Kursupplägg

Föreläsningar och inlämningsuppgifter.

Behörighet

Kunskaper i teoretisk datalogi motsvarade DD1352 Algoritmer, datastrukturer och komplexitet eller DD2352 Algoritmer och komplexitet krävs.

Litteratur

Se beskrivning på kurswebbsidan.

Examination

  • EXA1 - Examination, 6,0, betygsskala: P, F

Krav för slutbetyg

Godkända inlämningsuppgifter och föreläsningsanteckningar.

Ges av

EECS/Teoretisk datalogi

Examinator

Jakob Nordström <jakobn@kth.se>

Versionsinformation

Kursplan gäller från och med HT2014.
Examinationsinformation gäller från och med VT2019.