211service.com
Den enkla lösningen
När Daniel Spielman satt i en rättssal och väntade på att ta reda på om han skulle bli vald till juryuppdrag, fick Daniel Spielman en uppenbarelse - allt arbete han och kollegan Shanghua Teng hade byggt upp under de senaste tre åren var ett korthus. Jag kommer aldrig att glömma, säger Spielman, docent i matematik. Som jag satt där och väntade - som tur är inte att bli utvald – jag hade den här hemska upplevelsen av att inse att allt vi hade gjort var fel. Jag tänkte slänga mitt forskningsprogram. Och i det ögonblicket kollapsade korten.
Paret hade försökt hitta ett sätt att förbättra simplexmetoden, en av de mest använda algoritmerna i världen. Det gör det möjligt för många av de komplexa system som vi tar för givna - som telekommunikationsnätverk och schemaläggning för flottor av leveransfordon eller flygbolag - att fungera så effektivt och billigt som möjligt. Som ny biträdande professor ville Spielman etablera sig inom matematikens värld och få anställning vid MIT genom att arbeta med en stor utmaning, nämligen att göra algoritmen enklare, snabbare och bättre. Men efter den dagen i tingshuset, när han insåg att det var en återvändsgränd att tillämpa koncept från ett orelaterade område till simplexalgoritmen, visste han att han skulle behöva hitta ett nytt stort genombrott för att nå sina mål.
Några dagar senare, som en person vars hem har förstörts av en orkan eller tornado, började Spielman rädda det som fanns kvar av hans ruin av forskning. Och det var då den riktigt stora idén slog till: även om hans arbete inte kunde förbättra simplexmetoden, kanske det kunde det förklara det . Metoden hade utvecklats 1947, men efter mer än 50 års analyser hade ingen kunnat lista ut varför den fungerade. Spielmans aning visade sig vara rätt. Efter ytterligare tre års samarbete och hundratals matematiska formler kan han och Teng, professor vid Boston University, nu förklara varför simplexmetoden fungerar. Detta kan göra det möjligt för de så kallade optimeringsexperterna att lösa ännu mer komplexa organisatoriska problem. Redan har förklaringen, kallad smoothed analysis, citerats av National Science Foundation som ett stort framsteg inom informationsteknologi.
Vägen till upptäckt
Spielman och Teng träffades första gången hösten 1990, när Spielman, då student vid Yale University, besökte Carnegie Mellon University för att hålla ett tal. Teng, doktorand där, säger att han och andra på universitetet beundrade denna långhåriga collegejunior. Han hade redan två uppsatser av doktorskvalitet. Naturligtvis var han en av de mest prisade blivande studenterna som alla toppuniversitet ville locka till sina doktorandprogram. 1992 valde Spielman MIT. Teng kom samma år som instruktör vid institutet. Deras elev-lärarrelation blev snart vänskap och sedan ett samarbete som pågått i 11 år.
1996, efter flera års samarbete inom ett annat område, började duon försöka förbättra simplexmetoden. Forskningsprocessen är ungefär som att försöka hitta skatter på en mörk ö med en liten ficklampa, säger Teng. Vi försökte utforska de många hoppfulla ledtrådarna. Dan för alltid detaljerade arbetsdagböcker, som systematiskt markerar kartorna över utforskningen.
Efter tre år av sådant arbete fick Spielman sin rättssal förverkligande. De två matematikerna ändrade sitt mål och attackerade det nya forskningsproblemet på allvar.
Teng, som då var docent vid University of Illinois i Urbana-Champaign, flyttade tillbaka till Massachusetts på sabbatsår och hyrde en lägenhet fem minuter från Spielman's. Efter det gjorde båda forskarna sina vardagsrum till arbetsplatser. Teng monterade en stor whiteboardtavla på sin vardagsrumsvägg. Spielman förvarade en bakom sin soffa.
Sedan dess pågick deras arbete tillsammans dygnet runt. Det var en av de sakerna där min fru klagade över att jag såg Shanghua mer än jag sett henne på några år, säger Spielman. Teng arbetade heltid på Akamai i Cambridge, men han gick till Spielmans lägenhet nästan varje kväll efter jobbet och på helgerna. Vi skulle stanna uppe i många timmar, förmodligen till två, och jobba, konstaterar Spielman. Teng tillägger, jag var som en adopterad medlem av Dans familj. Till och med deras katt, Chloe, blev så van vid vår närvaro att hon satte sig framför whiteboardtavlan och tittade uppmärksamt när vi satte upp den. Forskarna tackade Chloe i sina erkännanden av tidskriften.
För att hålla reda på deras arbete fortsatte Spielman sina arbetsdagböcker och skrev ner alla tankar och ekvationer som whiteboards innehöll innan han raderade dem. Idag står ett dussin av dessa 200-sidiga dagböcker i anteckningsbokstorlek i en bokhylla på hans kontor i Building 2. Han säger att cirka 60 procent av den information som tidskrifterna innehåller är arbete med utjämnad analys. Under tiden använde Teng en digitalkamera för att ta ett 40-tal fotografier av whiteboardtavlor innan de raderades.
Äntligen svar på varför
Resultatet av all denna forskning var svaret på den enkla frågan Varför? Spielman och Teng kom äntligen på varför simplexmetoden har fungerat så bra hela den här tiden. De gjorde det genom att utveckla ett nytt sätt att analysera algoritmen.
Fram till upptäckten mätte de flesta matematiker algoritmer med hjälp av worst-case-analys, där en algoritm ges de svåraste uppgifterna och sedan bedöms utifrån hur väl den kan beräkna med den. Det skulle vara som om någon gav dig det värsta tänkbara långdivisionsproblem du kunde föreställa dig och sedan testade för att se om du kunde lösa det och hur lång tid det skulle ta. Men det här fungerade helt enkelt inte med simplexmetoden.
Så Spielman och Teng hittade ett nytt tillvägagångssätt. De introducerade viss variation i värsta tänkbara analyser. Istället för att använda exakta siffror som indata för att testa algoritmen tillät de oprecision. Till exempel, om inmatningen var 1,31, tillät de en slumpmässig inmatning mellan 1,29 och 1,33. De upptäckte att genom att tillåta oprecision, löste simplexalgoritmen alltid problemet effektivt, och det är därför den har varit så framgångsrik.
Idén låter enkel, men matematiken som stöder den är komplex. Spielman och Tengs första journalartikel i ämnet, som nu granskas av Association for Computing Machinery's Journal of the ACM , innehåller 80 sidor ekvationer. Jag vet inte om så många människor kunde gå igenom tidningen, säger Spielman. Att skriva tidningen förvirrade faktiskt till och med Spielman och Teng ibland. Ett par gånger slängde vi bara ut det som skrevs och skrev på nytt, för om det var komplicerat för oss skulle det bli ännu mer komplicerat för [andra] människor, säger Spielman.
Spielman och Teng har presenterat sina resultat runt om i världen till entusiastisk respons. De publicerade ett konferensbidrag 2001, och sedan dess har båda hållit inbjudna presentationer och huvudtal i hela USA och i Kina, Turkiet, Italien, Schweiz och Danmark.
Denna utjämnade analys är en viktig utveckling, säger Michel Goemans, PhD '90, en MIT-professor i tillämpad matematik. Och David Johnson, chef för avdelningen för algoritmer och optimering vid AT&T Labs-Research, säger, [Smoothed analysis] ger en extra nivå av självförtroende för dem som använder simplexmetoden.
Spielman säger att han inte har tagit fram sin whiteboardtavla sedan förra sommaren, när journalpappret äntligen var klart, men utan det hade vi aldrig lyckats skriva tidningen. Nu rekommenderar Spielman att unga forskare köper stora whiteboardtavlor som ett bra första steg mot genombrott. Teng tillskriver dock en stor del av deras framgång Spielmans dynamiska sinne och goda smak i att välja forskningsproblem. Han har alltid modet att arbeta med det svåraste öppna problemet på området, säger Teng, och det kan vara en ännu bättre utgångspunkt för forskare och nyfikna människor överallt.