Numero

Veckobladet om forskning, undervisning och
administration, m.m.

Nummer 20 · 25 maj 2000 · Årgång 30       

NADA

I vimlet på Nada:s terminavslutning!

Ljusgården lös upp mer än vanligt i fredags av alla glada ansikten som hade samlats för att delta i Nada:s terminavslutning. Det var dags för personer som utmärkt sig under året att hyllas och andra Nadaframgångar att applåderas i allmänhet. Nada:s prefekt, Ingrid Melinder, såg väldigt belåten ut när hon framförde sitt beröm med hjälp av den mycket entusiasmerande intervjuaren Olle Bälter och hans doa-kör. Ett annorlunda men slagkraftigt framträdande som fick gästerna att lyssna uppmärksamt.

 Marknadsföring

 En rejäl marknadsföring hade bekostats för att locka intresset  bland de anställda. Dyra annonser i Numerotidningen liksom  affischer och "flyers" var en del av mediaplanen. "Thank  God It's Friday" löd rubrikerna, en slogan som uppenbarligen  är stulen från ett välkänt amerikanskt franchise förtetag och  troligen kommer att ge Nada tunga ekonomiska efterföljder.  Men det var det nog värt. Reklamsatsningen hade lönat sig  och ett hundratal gäster trängdes i kändisvimlet. Fotografer  från tidningar som Numero jobbade förbrilt med att fånga de  ögonblick och gäster som uppenbarade sig.


Ingrid Melinder blir intervjuad av Olle Bälter med kören
ståendes till vänster, beredda att fylla i med sina sköna
stämmor mellan Bälters frågor.                               
"Ally McBeal"

Inspirationen till utformningen av denna fredagseftermiddag kommer ursprungligen från den amerikanska tv-serien "Ally McBeal", där kollegorna på en advokatfirma i New York träffas på kvällarna efter jobbet på den glamorösa nattklubben några trappor ned. Denna fiction speglar en kväll nu inte långt i från Nada.s verklighet skulle jag vilja påstå. Rykten säger att det är prefekten själv som är en trogen tittare och upphovskvinna till idén. Hursomhelst så lyckades det. Alla inslag fanns med. Buffén var utsökt och fanns i öveflöd. Musiken hade heller inte glömts bort. Kvällen inleddes med en behaglig pianobarsmusik och avslutades med gittarspelande och sång från Henry Rodriguez, IPLab.

Årets lärare!


Några av de personer som uppmärksammades under intervjun med Ingrid Melinder var Gerd Eriksson och Ninni Carlsund som båda har utsetts till årets lärare på D respektive I- programmen. Här syns Gerd Eriksson i bild till höger, provsmakandes av den goda buffén och omgiven av Germund Dahlquist t.v. och Sten Säfholm t.h på bilden.

 

 



Från vänster: Germund Dahlquist, Gerd Eriksson och Sten Säfholm.

 

Rickard Buch

Disputation


Jag disputerar fredagen 26/5 klockan 10.00 i sal E2. Titeln på
avhandlingen är "Some New Randomized Approximation Algorithms" och en sammanfattning bifogas nedan.
Hälsningar,


Gunnar Andersson

Abstract
The topic of this thesis is approximation algorithms for optimization
versions of NP-complete decision problems. No exact algorithms with sub-exponential running times are known for these problems, and therefore approximation algorithms with polynomial running times are studied. An approximation algorithm does not necessarily find the optimal solution, but it leaves a guarantee of how far from the optimum the output solution can be in the worst case. This
performance guarantee is the measure of quality of an approximation algorithm; it should be as close to 1 as possible.
We present new approximation algorithms for several
different maximization problems.
All problems are essentially constraint satisfaction problems: An instance consists of a set of constraints on groups of variables.
The objective is to satisfy as many of the constraints as possible.
Most results on such problems are for binary variables;
we give some results for binary variables and some where the
domain is the integers modulo p.
A common feature of all such problems is that they can be
approximated within a constant factor by picking a variable
assignment uniformly at random.
Until recently, this was the best known approximation algorithm
for many constraint satisfaction problems.
Algorithms based on semidefinite programming were introduced by
Goemans and Williamson in 1994, and they revolutionized the field.
We continue this line of research and use semidefinite programming
combined with randomized rounding schemes to obtain algorithms
better than picking a solution at random for several different
problems: Max Set Splitting, Max 3-Horn Sat, Max E2-Lin mod p,
and Max p-Section.
When restricted to dense instances, most such problems become easier to approximate.
We devise a polynomial time approximation scheme for the family
Max Ek-Function Sat mod p of constraint satisfaction
problems for which the domain is the integers modulo p.
We also prove lower bounds on the approximability of
Max k-Horn Sat and Max E2-Lin mod p.
A lower bound in this context is a proof that it is impossible to
approximate a problem within some given performance guarantee
unless P=NP.

TCS-seminarium

TCS-seminarium tisdagen den 30 maj klockan 15:15 i rum 1537.
Talare: Johan Håstad, Nada, KTH.
Titel: Some optimal inapproximability results.

Sammanfattning:
Using very efficient probabilistically checkable proofs (PCP) for
NP we prove that unless NP=P, some simple
approximation algorithms for basic NP-hard optimization problems are
essentially optimal. In particular given a SAT formula with exactly
3 variables in each clause it is not hard to find an assignment
that satisfies a fraction 7/8 of the clauses. We prove that (upto an
arbitrary epsilon>0) this is the best possible for a
polynomial time approximation algorithm.
In this talk we concentrate on the problem of given a linear system of
equations mod 2, to satisfy the maximal number of equations. This
problem is easy to approximate within a factor of 2 and we prove
that this is essentially tight. This result is obtained by
constructing a PCP that uses logarithmic randomness, reads 3 bits
in the proof and accepts based on the exclusive-or of the these bits.
This proof system has completeness 1-epsilon and soundness
1/2+epsilon, for any constant epsilon>0.


Välkommen till IPLabseminarium,

fredagen den 26 maj, 9.15-10.00
seminarierum 1625, plan 6, Lindstedtsv 3


Ambjörn Naeve håller ett seminarium med titeln Conzilla - A conceptual exploration and presentation tool that supports distributed learning.

PÅ GÅNG

Semester

Snart stundar än härlig semestertid för oss. Alla sekreterare, Christer Westerholm, Sten Säfholm samt Tina och undertecknad har bestämt sig. En sammanställning har gjorts över hur alla har semester under juni-juli-augusti. Den finns hos alla sekreterare. Dessutom finns sammanställningen uppsatt på dörren till Ann-Sofie och Inga-Britts arbetsrum på plan 4 (rum 1419).


Semesteransökan
Alla (utom undantagen se nedan) semesteransökningar för perioden juni-augusti ska vara mig till handa senast den 8 juni. Semesteransökan ska vara signerad av er närmaste arbetsledare innan den läggs i mitt postfack. Jag vill att alla som har sparade semesterdagar kontrollera detta (på lönebeskedet). Om du nått taket 40 dagar så måste samtliga årets semesterdagar tas ut. KTH tillåter inte att anställda har fler än 40 sparade dagar vilket innebär att dagarna utöver 40 nollas vid årets slut. Ledighetsblanketten kan hämtas från KTHs hemsida (internt+blankettarkivet+ personal). Jag vill även påminna de personer som har haft ledigt under året, och som inte har lämnat ledighet-sansökan, att den måste lämnas in senast den 8 juni. Är det någon som på grund av arbetets art inte vet innan den 8 juni hur semestern kan förläggas ska den ändå lämna in ansökan och korrigera den i efterskott. Följande yrkesgrupper är undantagna från att lämna in semesteransökan: professorer, forskare, forskarassistenter, lärare och doktorander. För samtliga gäller att önskar du spara semesterdagar måste prefekten godkänna detta.


Karensdag
När du blir sjuk är första sjukdagen en karensdag vilket innebär att du inte erhåller någon lön. Du som har rätt till fler än 20 betalda semesterdagar har möjlighet att byta karensdagen mot en semesterdag. På blanketten (som finns i blankettarkivet) för sjukanmälan finns en ruta som ska markeras om du vill byta ut karensdagen mot en semesterdag.


Vaktmästeriet
Christer har semester under perioden 4/6-16/7. Det är flera som kommer att se till att Christers arbetsuppgifter fungerar under hans semester. Har du några frågor får du höra av dig till mig.


Post till Cvap
Från och med den 5 juni kommer vi att ändra rutinen för hanteringen av posten till Cvap
Idag tar Christer en promenad till Cvap för att lämna och hämta post. Den nya rutinen är att KTH posten kommer att leverera Cvaps post direkt till Fiskartorpsvägen. Har du post till Cvap ska den läggas i ugående post vid postfacken på plan 4.
Arbetstid den 31 maj
Arbetstiden onsdagen den 31 maj är 8 timmar.


Sekreterarna är på kongress
Nästan samtliga sekreterare är på kongress i Uppsala den 5-6 juni.


Nyanställda
Följande personer har fått anställning på Nada
Lars Forsberg, forskningsingenjör på PDC t o m 2001-03-31.
Magnus Ahltorp, programutvecklare på systemgruppen t o m 2000-10-31.
Personerna kommer att presentera sig närmare i Numero vid ett senare tillfälle
Välkommen till oss på Nada.


Personer som slutar
Lars Arvestad, doktorand TCS har slutat
Staffan Ulfberg, doktorand TCS har slutat
Annika Hansèn-Eriksson, forskningsingenjör IPLab slutar 5/6
Ernesto Poletto, systemadministratör på systemgruppen slutar den 7 juni

Lars-Åke Lidström , utredare på KTHNoc slutar 8/6
Vi önskar dem lycka till med nya utmaningar i yrkeslivet


Eva-Lena

 
 

Nyheter från Systemgruppen!

Systemgruppens servicecenter Delfi inför sommartid mellan 19/6 och 18/8.
Det betyder att mottagningen är bemannad för både personliga besök ochtelefonsamtal vardagar mellan 10 och 12.
Övrig tid hänvisar vi till system@nada.kth.se.
Den 21/8 öppnar vi som vanligt igen.
Trevlig sommar!


Ernesto och Mikael


Course in Computational Fluid Dynamics


A graduate course in Computational Fluid Dynamics (CFD) by the
National Graduate School in Scientific Computing (NGSSC)
is announced, cf.
http://www.math.ntnu.no/cse/ngssc/announce.html
http://www.tdb.uu.se/~bernd/cfd/
The first part on incompressible flow computation will be given on June 5-9, 2000 by the Department of Mathematical Sciences, Norwegian University of Science and Technology,
Trondheim. The second part on compressible flow computation
will be organized on August 20-25, 2000 by the Department of Scientific Computing (TDB), Uppsala University. CFD projects will be handed out at Trondheim and presented at Uppsala.
Deadline for registration is May 27, 2000, cf.
http://www.math.ntnu.no/cse/ngssc/registration.html
Information on accomodation at Trondheim is available on
http://www.math.ntnu.no/cse/ngssc/det_trd.html

Sincerely,
Bernhard Müller
Department of Scientific Computing
Information Technology
Uppsala University
P.O. Box 120
S-751 04 Uppsala
Sweden
phone +46-18-4712975
fax +46-18-523049
e-mail bernd@tdb.uu.se
homepage http://www.tdb.uu.se/~bernd

Numero är institutionstidningen vid Nada – institutionen för numerisk analys och datalogi, KTH. Numero utkommer normalt på fredags­förmiddagar under teminstid. Manus måste lämnas in före kl.16 på tisdagar.

Manus, tips, förslag och andra bidrag till Numero kan lämnas på något av följande sätt:

Bidrag för artiklar och notiser bör i största möjliga mån vara färdigformulerade och korrekturlästa.

Varje Numeronummer utkommer i två former:

Numeroredaktionen består av Rickard Buch. Ansvarig utgivare är Ingrid Melinder. Numeros innehåll uttrycker inte institutionens officiella ståndpunkt annat än då detta anges.

Ibland refereras till Numeropärmen. Det är en pärm som finns i bokhyllan i Nadas fikarum på plan 4, i vilken kompletterande information sätts in, försett med nummer på formen 99:NN-N.

Kalendarium

fre. 26 maj

kl. 10.00

 

 

kl. 9.15-10.00

Gunnar Andersson disputerar i sal E2. Titeln på avhandlingen är "Some New Randomized Approximation Algorithms".


IPLab seminarium. Seminarierum 1625, plan 6, Lindstedtsv 3.
Ambjörn Naeve håller ett seminarium med titeln Conzilla - A conceptual exploration and presentation tool that supports distributed learning.

tis. 30 maj kl. 15:15 TCS-seminarium i rum 1537. Talare: Johan Håstad, Nada, KTH.
Titel: Some optimal inapproximability results.

 

Veckans Citat: "Three o'clock is always too late or too early for anything you want to do."

Jean Paul Sartre