Wijdverbreid Geloof Over Online Algoritmen
Inleiding
In het leven moeten we soms beslissingen nemen zonder alle informatie die we willen; dat geldt ook voor computerwetenschappen. Dit is het domein van online-algoritmen — die, ondanks hun naam, niet per se het internet betrekken. In plaats daarvan zijn dit probleemoplossingsstrategieën die reageren op gegevens zodra deze binnenkomen, zonder enige kennis van wat er daarna kan gebeuren. Dat vermogen om met onzekerheid om te gaan, maakt deze algoritmen nuttig voor raadsels in de echte wereld, zoals het beheren van het geheugen op een laptop of het kiezen van welke advertenties moeten worden weergegeven aan mensen die op internet surfen.
Onderzoekers bestuderen algemene versies van deze problemen om nieuwe methoden te onderzoeken om ze aan te pakken. Een van de bekendste is het "k-serverprobleem", dat de lastige taak beschrijft van het sturen van een vloot agenten om verzoeken die één voor één binnenkomen, uit te voeren. Het kunnen reparateurs, brandweerlieden of zelfs rondreizende ijsverkopers zijn.
"Het is heel eenvoudig om dit probleem te definiëren", aldus Marcin Bieńkowski, een algoritmeonderzoeker aan de Universiteit van Wrocław in Polen. Maar het "blijkt bizar moeilijk te zijn." Sinds onderzoekers eind jaren 80 het k-serverprobleem begonnen aan te pakken, hebben ze zich afgevraagd hoe goed online algoritmen deze taak aankunnen.
In de loop der decennia begonnen onderzoekers te geloven dat er een bepaald niveau van algoritmische prestaties is dat je altijd kunt bereiken voor het k-serverprobleem. Dus ongeacht met welke versie van het probleem je te maken hebt, er zal een algoritme zijn dat dit doel bereikt. Maar in een artikel dat in november voor het eerst online werd gepubliceerd, lieten drie computerwetenschappers zien dat dit niet altijd haalbaar is. In sommige gevallen schiet elk algoritme tekort.
"Ik ben blij te kunnen zeggen dat het een grote verrassing voor me was", zei Anupam Gupta, die algoritmen bestudeert aan de Carnegie Mellon University en niet betrokken was bij het artikel. Het werk biedt "diepere inzichten in het centrale probleem op dit gebied."
Computerwetenschappers schetsten dit probleem voor het eerst in 1988. Om er een idee van te krijgen, stellen we ons een bedrijf voor dat loodgieters in dienst heeft. Als er telefoontjes binnenkomen, moet het bedrijf beslissen welke loodgieter naar welke locatie gaat. Het doel van het bedrijf - en het doel van een algoritme voor het k-serverprobleem - is om de totale afstand die door alle loodgieters wordt afgelegd, te minimaliseren.
Het lastige is dat het bedrijf niet van tevoren weet waar de telefoontjes vandaan komen. Als dat wel zo was, zou het kunnen vertrouwen op een "offline-algoritme" dat de toekomst kent. In het bijzonder zou het een ideale dispatchingstrategie kunnen gebruiken die een oplossing vindt met de minste totale reis voor elke reeks telefoontjes. Geen enkel online-algoritme kan het ooit verslaan of zelfs maar betrouwbaar evenaren.
Maar onderzoekers willen zo dicht mogelijk bij de werkelijkheid komen. Ze meten de prestaties van een online algoritme door de reisafstand in elke strategie te vergelijken en berekenen wat bekend staat als de concurrentieverhouding. Algoritmeontwerpers proberen online strategieën te ontwikkelen die het offline ideaal benaderen, door deze verhouding terug te brengen tot 1.
Om er zeker van te zijn dat geen enkel algoritme een concurrentieverhouding van log k zou kunnen bereiken, bouwden de auteurs een familie van complexe ruimtes, verzamelingen van punten die een agent zou kunnen vereisen om te bezoeken; elke opeenvolgende ruimte bestaat uit kopieën van de laatste.
Stel je voor dat ons loodgietersbedrijf slechts twee loodgieters heeft en dat het slechts één lange straat bedient. De oproepen komen één voor één binnen. Een redelijke eerste aanpak, bekend als het hebzuchtige algoritme, zou zijn om de loodgieter te sturen die het dichtst bij de locatie van elke inkomende oproep is. Maar hier is een scenario waarin dit algoritme worstelt: stel je voor dat de ene loodgieter aan de westkant van de straat begint en de andere aan de oostkant, en alle oproepen komen van twee aangrenzende huizen aan de westkant. In dat geval verhuist de ene loodgieter nooit, terwijl de andere kilometers maakt bij die twee huizen. Achteraf gezien was de beste strategie geweest om beide loodgieters naar het probleemgevoelige gebied te verplaatsen, maar helaas had je niet kunnen weten waar dat zou zijn.
Toch, zei Bieńkowski, is het mogelijk om het beter te doen dan het hebzuchtige algoritme. Het algoritme "dubbele dekking" verplaatst beide loodgieters met dezelfde snelheid naar elk telefoontje dat tussen hen in valt, totdat een van hen het bereikt. Deze methode bereikt een lagere concurrentieverhouding dan het hebzuchtige algoritme.
Hoewel dit abstracte probleem niet relevant is voor echte loodgietersbedrijven, "is het k-serverprobleem zelf echt de bepalende vraag" in online computing, zei Yuval Rabani, een computerwetenschapper aan de Hebreeuwse Universiteit van Jeruzalem die medeauteur was van het recente artikel. Dat komt deels doordat tools en technieken die zijn ontwikkeld tijdens het werken aan het k-serverprobleem, vinden vaak toepassingen elders in de studie van online-algoritmen, en zelfs daarbuiten.
"Dit is onderdeel van de magie van het werken aan algoritmen", zei hij.
Yuval Rabani hielp een decennia-oude veronderstelling te ontkrachten over de prestaties die je van bepaalde algoritmen kunt verwachten. Foto Aviv Zohar
Wanneer ze deze problemen bestuderen, zien wetenschappers ze graag als spellen tegen een tegenstander. De tegenstander kiest een duivelse reeks verzoeken om het online-algoritme zo slecht mogelijk te laten presteren in vergelijking met zijn offline-tegenhanger. Om de tegenstander van een deel van zijn kracht te beroven, gebruiken onderzoekers algoritmen die willekeurige beslissingen bevatten.
Deze strategie is behoorlijk effectief en onderzoekers vermoeden al sinds het begin van de jaren negentig dat je altijd een gerandomiseerd algoritme kunt vinden dat een specifiek prestatiedoel bereikt: een competitieve verhouding evenredig aan log k, waarbij k het aantal agenten is. Dit wordt de gerandomiseerde k-server-conjectuur genoemd en onderzoekers hebben aangetoond dat dit voor sommige ruimtes of specifieke verzamelingen punten (het equivalent van huizen die loodgieters kunnen bellen) geldt. Maar het is niet voor alle gevallen bewezen.
Zoals de meeste onderzoekers dachten Rabani en zijn coauteurs — Sébastien Bubeck van Microsoft Research en Christian Coester van de Universiteit van Oxford — dat de conjectuur waar was. "Ik had geen reden om eraan te twijfelen," zei Coester.
Maar dat begon te veranderen toen ze aan een ander online probleem werkten. Het had verbindingen met het k-serverprobleem en de bekende ondergrens voor de concurrentieverhouding was onverwacht hoog. Het deed hen denken dat een doel zo laag als log k voor het k-serverprobleem misschien te optimistisch was.
Rabani zei dat het Coester was die als eerste suggereerde dat de gerandomiseerde k-server-conjectuur onjuist zou kunnen zijn. "Zodra hij het zei, klopte het allemaal."
Om de veronderstelling te ontkrachten, speelden de auteurs de tegenstander en creëerden ze een perfecte storm die zou voorkomen dat een online algoritme een concurrerende verhouding van log k zou bereiken. Hun strategie bestond uit twee delen: ze construeerden een familie van complexe, fractalachtige ruimtes en ontwierpen een distributie van verzoeksequenties die moeilijk zou zijn voor elk mogelijk algoritme. Bij de allereerste zet van het algoritme betekende de structuur van de ruimte dat het moest kiezen tussen twee identieke paden, waarvan er één uiteindelijk extra reizen zou vereisen op basis van de verzoeken. Vervolgens gebruikten de auteurs een methode genaamd recursie om ruimtes te bouwen die deze beslissingspunten vermenigvuldigden, waardoor het algoritme in een moeras van slechte opties terechtkwam en de kosten omhoog gingen.
De keuzes deden Rabani denken aan het gedicht "The Road Not Taken" van Robert Frost, waarin een reiziger twee mogelijke paden door een geel bos overweegt. "We passen het gedicht gewoon recursief toe", grapte hij. "En dan gaat het echt slecht."
De auteurs toonden aan dat in de ruimtes die ze hadden geconstrueerd, een gerandomiseerd algoritme nooit een competitieve verhouding kan bereiken die beter is dan (log k)2, waardoor een universeel doel van log k voor altijd buiten bereik komt. Ze hadden de veronderstelling weerlegd.
Gerelateerd
Dit werk, dat een Best Paper Award won op het Symposium on Theory of Computing van 2023, markeert een "solide theoretische" mijlpaal, zei Gupta. Dit soort resultaten helpt om aan te geven wat voor soort prestaties we van onze algoritmen kunnen verwachten. In de praktijk plannen algoritmeontwerpers echter vaak niet rond het ergste scenario, met een almachtige tegenstander en volledige onwetendheid over de toekomst. Wanneer algoritmes worden losgelaten op echte problemen, overtreffen ze vaak de theoretische verwachtingen.
Het artikel, dat ook grenswaarden bewees voor gerandomiseerde algoritmes die voor andere problemen worden gebruikt, zou ook implicaties kunnen hebben voor toekomstig werk op dit gebied. Het resultaat "benadrukt duidelijk de kracht" van de techniek die de auteurs gebruikten, zei Gupta.
Misschien tarten die toekomstige bevindingen de verwachtingen van onderzoekers, zoals deze deed, zei Rabani. "Dit is een van de gevallen waarin het echt goed voelt om ongelijk te hebben."
Nan Cao voor Quanta Magazine
