211service.com
Den simple løsning
Mens Daniel Spielman sad i en retssal og ventede på at finde ud af, om han ville blive valgt til nævningeting, fik Daniel Spielman en åbenbaring - alt det arbejde, han og kollegaen Shanghua Teng havde bygget op i løbet af de sidste tre år, var et korthus. Jeg glemmer aldrig, siger Spielman, der er lektor i matematik. Som jeg sad der og ventede - heldigvis ikke at blive valgt - jeg havde denne forfærdelige oplevelse af at indse, at alt, hvad vi havde gjort, var forkert. Jeg tænkte på at smide mit forskningsprogram. Og i det øjeblik faldt kortene sammen.
Parret havde forsøgt at finde en måde at forbedre simplex-metoden, en af de mest udbredte algoritmer i verden. Det gør det muligt for mange af de komplekse systemer, vi tager for givet - såsom telekommunikationsnetværk og planlægning af flåder af leveringskøretøjer eller flyselskaber - at arbejde så effektivt og billigt som muligt. Som ny adjunkt ønskede Spielman at etablere sig inden for matematikkens verden og få ansættelse på MIT ved at arbejde på en stor udfordring, nemlig at gøre algoritmen enklere, hurtigere og bedre. Men efter den dag i retsbygningen, da han indså, at det var en blindgyde at anvende begreber fra et ikke-relateret område til simpleksalgoritmen, vidste han, at han skulle finde endnu et stort gennembrud for at nå sine mål.
Et par dage senere begyndte Spielman, som en person, hvis hjem er blevet ødelagt af en orkan eller tornado, at redde det, der var tilbage af hans ruin af forskning. Og det var da den helt store idé ramte: Selvom hans arbejde ikke kunne forbedre simplex-metoden, kunne det måske Forklar det . Metoden var blevet udviklet i 1947, men efter mere end 50 års analyser havde ingen kunnet finde ud af, hvorfor den virkede. Spielmans anelse viste sig at være rigtig. Efter yderligere tre års samarbejde og hundredvis af matematiske formler kan han og Teng, professor ved Boston University, nu forklare, hvorfor simpleksmetoden virker. Dette kan give de såkaldte optimeringseksperter mulighed for at løse endnu mere komplekse organisatoriske problemer. Allerede nu er forklaringen, kaldet smoothed analysis, blevet citeret af National Science Foundation som et stort fremskridt inden for informationsteknologi.
Vejen til opdagelse
Spielman og Teng mødtes første gang i efteråret 1990, da Spielman, der dengang var bachelor ved Yale University, besøgte Carnegie Mellon University for at holde en tale. Teng, en ph.d.-kandidat der, siger, at han og andre på universitetet beundrede denne langhårede college-junior. Han havde allerede to artikler af ph.d.-kvalitet. Naturligvis var han en af de mest værdsatte potentielle studerende, som alle topuniversiteter ønskede at tiltrække til deres ph.d.-uddannelser. I 1992 valgte Spielman MIT. Teng ankom samme år som instruktør på instituttet. Deres elev-lærer-forhold blev hurtigt venskab og derefter et samarbejde, der har varet 11 år.
I 1996, efter flere års arbejde sammen på et andet område, begyndte duoen at søge at forbedre simplex-metoden. Forskningsprocessen er meget som at forsøge at finde skatte på en mørk ø med en lille lommelygte, siger Teng. Vi prøvede at udforske de mange håbefulde spor. Dan fører altid detaljerede arbejdsjournaler, som systematisk markerer kortene over udforskningen.
Efter tre år med sådant arbejde fik Spielman sin retssalsrealisering. De to matematikere ændrede deres mål og angreb det nye forskningsproblem for alvor.
Teng, som på det tidspunkt var lektor ved University of Illinois i Urbana-Champaign, flyttede tilbage til Massachusetts på sabbatår og lejede en lejlighed fem minutter væk fra Spielman's. Derefter forvandlede begge forskere deres stuer til arbejdsrum. Teng monterede en stor tavle på sin stuevæg. Spielman opbevarede en bag sin sofa.
Fra da af foregik deres arbejde sammen på alle tidspunkter. Det var en af de ting, hvor min kone klagede over, at jeg så Shanghua mere, end jeg så hende i et par år, siger Spielman. Teng arbejdede fuld tid hos Akamai i Cambridge, men han tog til Spielmans lejlighed næsten hver aften efter arbejde og i weekenden. Vi ville være oppe i mange timer, formentlig til to, og arbejde, konstaterer Spielman. Teng tilføjer, jeg var som et adopteret medlem af Dans familie. Selv deres kat, Chloe, blev så vant til vores tilstedeværelse, at hun satte sig foran tavlen og kiggede opmærksomt på, når vi satte den op. Forskerne takkede Chloe i deres journalpapirs anerkendelser.
For at holde styr på deres arbejde fortsatte Spielman sine arbejdsdagbøger og skrev ned hver tanke og ligning, som tavlerne indeholdt, før han slettede dem. I dag står et dusin af disse 200-siders journaler i notesbogsstørrelse langs en bogreol på hans Bygning 2-kontor. Han siger, at omkring 60 procent af de oplysninger, journalerne indeholder, er arbejde med udjævnede analyser. I mellemtiden brugte Teng et digitalkamera til at tage omkring 40 billeder af tavlerne, før de blev slettet.
Endelig svar på hvorfor
Resultatet af al denne forskning var svaret på det simple spørgsmål Hvorfor? Spielman og Teng fandt endelig ud af, hvorfor simplex-metoden har fungeret så godt hele tiden. De gjorde det ved at udvikle en ny måde at analysere algoritmen på.
Indtil deres opdagelse målte de fleste matematikere algoritmer ved at bruge worst-case-analyse, hvor en algoritme får de sværeste data og derefter bedømt på, hvor godt den kan beregne med dem. Det ville være, som om nogen gav dig det værst tænkelige langdivisionsproblem, du kunne forestille dig, og derefter testede for at se, om du kunne løse det, og hvor lang tid det ville tage. Men dette virkede bare ikke med simplex-metoden.
Så Spielman og Teng fandt en ny tilgang. De introducerede en vis variation i worst case-analyser. I stedet for at bruge nøjagtige tal som input til at teste algoritmen, tillod de unøjagtighed. For eksempel, hvis inputtet var 1,31, tillod de et tilfældigt input mellem 1,29 og 1,33. De opdagede, at ved at tillade unøjagtighed, løste simplex-algoritmen altid problemet effektivt, og det er derfor, det har været så vellykket.
Ideen lyder simpel, men den matematik, der understøtter den, er kompleks. Spielman og Tengs første journaloplæg om emnet, nu under revision af Association for Computing Machinery's Tidsskrift for ACM , indeholder 80 sider med ligninger. Jeg ved ikke, om så mange mennesker kunne gå gennem avisen, siger Spielman. Faktisk forvirrede skrivningen af papiret endda Spielman og Teng nogle gange. Et par gange smed vi bare det skrevet ud og skrev på ny, for hvis det var kompliceret for os, ville det blive endnu mere kompliceret for [andre] mennesker, siger Spielman.
Spielman og Teng har præsenteret deres resultater rundt om i verden til entusiastisk respons. De udgav et konferenceoplæg i 2001, og siden da har begge holdt inviterede præsentationer og hovedtaler i hele USA og i Kina, Tyrkiet, Italien, Schweiz og Danmark.
Denne udjævnede analyse er en vigtig udvikling, siger Michel Goemans, PhD '90, en MIT-professor i anvendt matematik. Og David Johnson, leder af afdelingen for algoritmer og optimering hos AT&T Labs-Research, siger: [Smoothed analysis] giver et ekstra niveau af selvtillid for dem, der bruger simplex-metoden.
Spielman siger, at han ikke har trukket sin tavle frem siden sidste sommer, hvor journalpapiret endelig var færdigt, men uden det ville vi aldrig have nået at skrive papiret. Nu anbefaler Spielman, at unge forskere køber store tavler som et godt første skridt mod at skabe gennembrud. Teng tilskriver dog en stor del af deres succes Spielmans dynamiske sind og gode smag i at vælge forskningsproblemer. Han har altid modet til at arbejde med det sværeste åbne problem på området, siger Teng, og det kan måske være et endnu bedre udgangspunkt for forskere og nysgerrige mennesker overalt.