Upp till webbsidan för doktorandseminarierna.
Informella doktorandseminarier i teoretisk datalogi höstterminen 2003
Höstterminen 2003 var det litet dålig fart på
doktorandseminarierna. Under andra halvan av hösten övertogs deras
funktion delvis av seminarierna på
doktorandkursen i
kretskomplexitet. Dock blev det faktiskt ett "äkta"
doktorandseminarium mot slutet av terminen.
-
8 december, kl 14.15, rum 1625:
Simplified Tight Analysis of Johnson's Algorithm
(Lars Engebretsen, Nada/TCS)
-
In their paper ``Tight Bound on Johnson's Algorithm for Maximum
Satisfiability'' [JCSS 58(3):622--640 (1999)] Chen, Friesen and Zheng
provided a tight bound on the approximation ratio of Johnson's
algorithm for Maximum Satisfiability [JCSS 9(3):256--278 (1974)]. We
give a simplified proof of their result.
Upp till webbsidan för doktorandseminarierna.
Sidansvarig: Jakob Nordström <jakobn~at-sign~nada~dot~kth~dot~se>
Senast ändrad 2 december 2005
Tekniskt stöd: <webmaster@nada.kth.se>