Rådmodellen för online beräkning fångar den inställning där online-algoritmen ges viss partiell information om begäran sekvens. Detta paradigm gör det möjligt att fastställa avvägningar mellan mängden av denna ytterligare information och prestanda för online-algoritmen. Till skillnad från verkliga livet där råd är en rekommendation som vi kan välja att följa eller ignorera baserat på pålitlighet, i den nuvarande rådgivningen modell, online algoritmen behandlar det som ofelbar. Detta innebär att om råden är korrupta eller, värre, om de kommer från en skadlig källa, algoritmen kan prestera dåligt. I detta arbete studerar vi online beräkning i en miljö där råden ges av en opålitlig källa. Vårt mål är att kvantifiera effekten av opålitliga råd för att designa och analysera online-algoritmer som är motståndskraftiga och presterar bra även när råden genereras på ett illvilligt, kontradiktoriskt sätt. I detta syfte fokuserar vi på välstuderade online-problem som skiduthyrning, online budgivning, bin packning och listuppdatering. För ski-hyra och online budgivning, visar vi hur man får algoritmer som är Pareto-optimal med avseende på de konkurrensförhållanden som uppnåtts; detta förbättrar på ramen för Puruhit et al. [NeurIPS 2018] där Pareto-optimalitet inte nödvändigtvis garanteras. För bin packning och listuppdatering, ger vi online-algoritmer med värsta fall kompromisser i sin konkurrenskraft, beroende på om råden är betrodda eller inte; detta motiveras av arbete Lykouris och Vassilvitskii [ICML 2018] på personsökning problem, men där konkurrenskraft beror på tillförlitligheten i råden.
REF kvantifierar ytterligare effekterna av rådgivningens kvalitet och föreslår Pareto-optimal algoritm för skiduthyrningsproblem.
Online Computation with Untrusted Advice
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}