Vi anser att online reser säljare problem (TSP), där förfrågningar visas online över tiden på den verkliga linjen och behöver besökas av en server som ursprungligen ligger vid ursprung. Vi skiljer mellan stängd och öppen online TSP, beroende på om servern så småningom behöver återvända till ursprunget eller inte. Medan online TSP på linjen är ett mycket naturligt online-problem som infördes för mer än två decennier sedan, ingen snäv konkurrensanalys var känd hittills. Vi löser detta problem genom att tillhandahålla snäva gränser för konkurrensförhållandena för både den stängda och den öppna varianten av problemet. Särskilt för slutna online TSP, tillhandahåller vi en 1.64-konkurrenskraftig algoritm, vilket motsvarar en känd lägre gräns. För öppen online TSP ger vi en ny övre gräns samt en matchande nedre gräns som fastställer det anmärkningsvärda konkurrensförhållandet på 2.04. Dessutom anser vi att online Dial-A-Ride problem på linjen, där varje begäran måste transporteras till en angiven destination. Vi erbjuder en förbättrad icke-förebyggande nedre gräns på 1,75 för denna inställning, samt en förbättrad förebyggande algoritm med konkurrensförhållande 2.41. Slutligen generaliserar vi kända och ger nya komplexa resultat för de underliggande offline-problemen. I synnerhet ger vi en algoritm med kör
Nyligen stängde REF konkurrensklyftan för OLTSP (dvs. författarna presenterade en 1.64-konkurrensalgoritm för problemet) och presenterade nya komplexa resultat för flera versioner av problemet offline Dial-A-Ride.
Tight Bounds for Online TSP on the Line
{'venue': 'SODA', 'journal': None, 'mag_field_of_study': ['Computer Science']}