Forskere afviser en udbredt overbevisning om onlinealgoritmer | Quanta Magasinet

I livet er vi nogle gange nødt til at træffe beslutninger uden al den information, vi ønsker; det er også rigtigt inden for datalogi. Dette er området for online-algoritmer - som på trods af deres navn ikke nødvendigvis involverer internettet. I stedet er disse problemløsningsstrategier, der reagerer på data, når de ankommer, uden nogen viden om, hvad der kan komme næste gang. Denne evne til at håndtere usikkerhed gør disse algoritmer nyttige til virkelige gåder, som at administrere hukommelse på en bærbar computer eller vælge, hvilke annoncer der skal vises til folk, der surfer på nettet.

Forskere studerer generaliserede versioner af disse problemer for at undersøge nye metoder til at tackle dem. Blandt de mest berømte er "k-serverproblem," som beskriver den vanskelige opgave at sende en flåde af agenter til at opfylde forespørgsler, der kommer ind én efter én. De kunne være reparationsteknikere eller brandmænd eller endda omstrejfende is-sælgere.

"Det er virkelig nemt at definere dette problem," sagde Marcin Bieńkowski, en algoritmeforsker ved universitetet i Wrocław i Polen. Men det "viser sig at være bizart svært." Siden forskere begyndte at angribe k-serverproblem i slutningen af ​​1980'erne, har de undret sig over, præcis hvor godt online algoritmer kan klare opgaven.

I løbet af årtierne begyndte forskere at tro, at der er et vist niveau af algoritmisk ydeevne, du altid kan opnå for k-server problem. Så uanset hvilken version af problemet du har at gøre med, vil der være en algoritme, der når dette mål. Men i et papir, der først blev offentliggjort online i november sidste år, skrev tre dataloger viste at dette ikke altid er muligt. I nogle tilfælde kommer enhver algoritme til kort.

"Jeg er glad for at kunne sige, at det var en stor overraskelse for mig," sagde Anupam Gupta, der studerer algoritmer ved Carnegie Mellon University og ikke var involveret i papiret. Værket giver "dybere indsigt i det centrale problem på dette område."

Dataloger først skitserede dette problem i 1988. For at få en fornemmelse af det, lad os forestille os en virksomhed, der beskæftiger blikkenslagere. Efterhånden som der kommer opkald, skal virksomheden beslutte, hvilken VVS-installatør der går til hvilket sted. Virksomhedens mål — og målet om en algoritme for k-serverproblem — er at minimere den samlede afstand, som alle blikkenslagere har tilbagelagt.

Det vanskelige er, at virksomheden ikke på forhånd ved, hvor opkaldene kommer fra. Hvis den gjorde det, kunne den stole på en "offline-algoritme", der kender fremtiden. Især kunne den bruge en ideel afsendelsesstrategi, der finder en løsning med den mindste samlede rejse for enhver række af opkald. Ingen online-algoritme kan nogensinde slå det, eller endda pålideligt matche det.

Men forskere vil gerne komme så tæt på som muligt. De måler en online-algoritmes ydeevne ved at sammenligne rejsedistancen i hver strategi og beregne det, der er kendt som konkurrenceforholdet. Algoritmedesignere forsøger at udforme onlinestrategier, der nærmer sig offlineidealet, og reducerer dette forhold til 1.

Lad os forestille os, at vores VVS-firma kun har to VVS-installatører, og det betjener kun en enkelt, lang gade. Opkaldene kommer et ad gangen. En rimelig første tilgang, kendt som den grådige algoritme, ville være at sende den blikkenslager, der er tættest på placeringen af ​​hvert indgående opkald. Men her er et scenarie, hvor denne algoritme kæmper: Forestil dig, at den ene blikkenslager starter i den vestlige ende af gaden og den anden i den østlige ende, og alle opkaldene kommer fra to nabohuse i den vestlige ende. I så fald flytter den ene blikkenslager sig aldrig, mens den anden samler flere kilometer ved de to huse. Set i bakspejlet ville den bedste strategi have været at flytte begge blikkenslagere til det problemfyldte område - men desværre kunne du ikke have vidst, hvor det skulle være.

Alligevel, sagde Bieńkowski, er det muligt at gøre det bedre end den grådige algoritme. Det "dobbelt dækning”-algoritmen flytter begge blikkenslagere i samme hastighed mod ethvert opkald, der falder mellem dem, indtil en af ​​dem når det. Denne metode opnår et lavere konkurrenceforhold end den grådige algoritme.

Selvom dette abstrakte problem ikke er relevant for rigtige VVS-firmaer, "den k-serverproblemet i sig selv er virkelig det afgørende spørgsmål" i online computing, sagde Yuval Rabani, en datalog ved det hebraiske universitet i Jerusalem, der var medforfatter til det nylige papir. Dels skyldes det, at værktøjer og teknikker udviklet under arbejdet med k-server problem ofte finde applikationer andre steder i studiet af online algoritmer, og endda uden for det.

"Dette er en del af magien ved at arbejde med algoritmer," sagde han.

Når de studerer disse problemer, kan forskerne gerne forestille sig dem som spil mod en modstander. Modstanderen vælger en djævelsk sekvens af anmodninger for at få onlinealgoritmen til at fungere så dårligt som muligt sammenlignet med dens offline-modstykke. For at berøve modstanderen noget af dens magt bruger forskere algoritmer, der bl.a tilfældige beslutninger.

Denne strategi er ret effektiv, og forskere har siden begyndelsen af ​​1990'erne haft mistanke om, at du altid kan finde en randomiseret algoritme, der når et specifikt præstationsmål: et konkurrenceforhold proportionalt med log kHvor k er antallet af agenter. Dette kaldes det randomiserede k-serverformodninger, og forskere har vist, at det er sandt for nogle rum eller specifikke samlinger af punkter (svarende til huse, der kunne kalde på blikkenslagere). Men det er ikke blevet bevist for alle tilfælde.

Som de fleste forskere, Rabani og hans medforfattere - Sébastien Bubeck af Microsoft Research og Christian Coester fra University of Oxford - regnede med, at formodningen var sand. "Jeg havde ingen grund til at tvivle på det," sagde Coester.

Men det begyndte at ændre sig, da de arbejdede på et andet online problem. Det havde forbindelser til k-serverproblem, og den kendte nedre grænse for konkurrenceforholdet var uventet høj. Det fik dem til at tænke på et mål så lavt som log k for k-serverproblemet var alt for optimistisk.

Rabani sagde, at det var Coester, der først foreslog, at den randomiserede k-serverformodning kan være falsk. "Så snart han sagde det, gav det hele mening."

For at modbevise formodningen spillede forfatterne modstanderen og skabte en perfekt storm, der ville forhindre enhver online-algoritme i at nå et konkurrencedygtigt forhold mellem log k. Deres strategi havde to dele: De konstruerede en familie af komplekse, fraktallignende rum og designede en fordeling af anmodningssekvenser, der ville være vanskelige for enhver mulig algoritme. På algoritmens allerførste træk betød strukturen af ​​rummet, at det skulle vælge mellem to identiske stier, hvoraf den ene i sidste ende ville kræve ekstra rejse baseret på anmodningerne. Derefter brugte forfatterne en metode kaldet rekursion til at bygge rum, der multiplicerede disse beslutningspunkter, hvilket tvang algoritmen ind i et morads af dårlige muligheder og øgede omkostningerne.

Valgene mindede Rabani om Robert Frost-digtet "Vejen ikke taget,”, hvor en rejsende overvejer to potentielle stier gennem en gul skov. "Vi anvender bare digtet rekursivt," jokede han. "Og så går det rigtig dårligt."

Forfatterne viste, at i de rum, de havde konstrueret, kan en randomiseret algoritme aldrig opnå et konkurrenceforhold bedre end (log k)², skubbe et universelt mål for log k for altid uden for rækkevidde. De havde tilbagevist formodningen.

Dette værk, der vandt en Pris for bedste papir ved 2023 Symposium om teori om computing, markerer en "solid teoretisk" milepæl, sagde Gupta. Denne form for resultat hjælper med at indikere, hvilken slags præstation vi kan håbe på fra vores algoritmer. I praksis planlægger algoritmedesignere dog ofte ikke omkring worst-case scenarier med en almægtig modstander og fuldstændig uvidenhed om fremtiden. Når algoritmer slippes løs på problemer i den virkelige verden, overstiger de ofte teoretiske forventninger.

Papiret, som også beviste cutoffs for randomiserede algoritmer, der bruges til andre problemer, kan også have konsekvenser for fremtidigt arbejde på området. Resultatet "fremhæver klart kraften" af den teknik, forfatterne brugte, sagde Gupta.

Måske vil disse fremtidige resultater trodse forskernes forventninger, som denne gjorde, sagde Rabani. "Dette er et af de tilfælde, hvor det føles rigtig godt at tage fejl."

Quanta gennemfører en række undersøgelser for bedre at kunne betjene vores publikum. Tag vores datalogisk læserundersøgelse og du vil være med til at vinde gratis Quanta varer.