I detta dokument introducerar vi onlinetjänsten med fördröjningsproblem. I detta problem finns det n-punkter i ett metriska utrymme som utfärdar serviceförfrågningar över tid, och en server som betjänar dessa förfrågningar. Målet är att minimera summan av den sträcka som skickas av servern och den totala förseningen (eller en strafffunktion) för att tillgodose förfrågningarna. Detta problem modellerar den grundläggande handeln mellan batching förfrågningar för att förbättra lokaliseringen och minska förseningar för att förbättra svarstiden, som har många tillämpningar i driftledning, operativsystem, logistik, försörjningskedjan förvaltning och schemaläggning. Vårt huvudsakliga resultat är att visa ett polylogaritmiskt konkurrensförhållande för onlinetjänsten med fördröjningsproblem. Detta resultat erhålls genom en algoritm som vi kallar den förebyggande servicealgoritmen. Den framträdande egenskapen hos denna algoritm är en process som kallas förebyggande tjänst, som använder en ny kombination av (rekursiv) tidsspedition och rumslig utforskning på ett metriska utrymme. Vi generaliserar också våra resultat till k > 1 servrar, och får starkare resultat för speciella mått såsom enhetliga och stjärnmått som motsvarar (viktade) personsökningsproblem. • Teori för beräkning → Online-algoritmer; KEYWORDS Pagning, viktad personsökning, k-server, online-algoritmer, konkurrensförhållande.
Ett relaterat problem är onlinetjänsten med fördröjningsproblem (OSD-problem) som infördes av Azar et al. Hoppa över det.
Online service with delay
{'venue': 'STOC 2017', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}