Vi anser online routing optimering problem där målet är att minimera den tid som behövs för att besöka en uppsättning platser under olika begränsningar; problemen är online eftersom uppsättningen av platser avslöjas stegvis över tiden. Vi anser två huvudsakliga problem: (1) online Traveling Salesman Problem (TSP) med företräde och kapacitet begränsningar och (2) online TSP med m säljare. För båda problemen föreslår vi online-algoritmer, var och en med ett konkurrensförhållande på 2; för m-säljare problemet, visar vi vårt resultat är bäst möjligt. Vi överväger också polynom-tid online algoritmer. Vi överväger sedan resursförstärkning, där vi ger onlineservrarna ytterligare resurser för att kompensera den kraftfulla offline-mottagarfördelen; på detta sätt riktar vi en huvudkritik mot konkurrensanalys. Vi tar hänsyn till de fall där online-algoritmen har tillgång till snabbare servrar, servrar med större kapacitet, ytterligare servrar och/eller avancerad information. Vi får förbättrade konkurrensförhållanden. Vi ger också lägre gränser för konkurrensförhållandena under resursökning, vilket i många fall är snävt och leder till bästa möjliga resultat. Slutligen studerar vi onlinealgoritmer ur en asymptotisk synvinkel. Vi visar att under allmänna stokastiska strukturer för problemdata, okända och oanvända av onlinespelaren, online algoritmer är nästan säkert asymptotiskt optimal. Dessutom tillhandahåller vi beräkningsresultat som visar att konvergensen kan vara mycket snabb.
Jaillet och Wagner REF har föreslagit en centraliserad deterministisk algoritm med ett konkurrensförhållande på 2 (den bästa möjliga lösningen).
Generalized Online Routing: New Competitive Ratios, Resource Augmentation and Asymptotic Analyses
{'venue': None, 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}