Online k-server routing problems

DOI10.1007/S00224-008-9103-4MaRDI QIDQ839628zbMATH OpenOpenAlexFDO

Authors Vincenzo Bonifaci, L. Stougie

Publication date 2 September 2009

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-008-9103-4

zbMATH Keywords

online algorithmscompetitive analysistraveling salesmantraveling repairmanserver routing

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• Online k-Server Routing Problems
• New lower bounds for online \(k\)-server routing problems
• The 3-server problem in the plane.
• Serving requests with on-line routing
• Competitive algorithms for the bicriteria \(k\)-server problem

Cites work

• scientific article; zbMATH DE number 1629830 (Why is no real title available?)
• scientific article; zbMATH DE number 1629851 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 1947058 (Why is no real title available?)
• scientific article; zbMATH DE number 2079396 (Why is no real title available?)
• scientific article; zbMATH DE number 3895002 (Why is no real title available?)
• Algorithms and Data Structures
• Algorithms for the on-line travelling salesman
• An adversarial queueing model for online server routing
• Competitive algorithms for server problems
• LATIN 2004: Theoretical Informatics
• LP-Based Online Scheduling: From Single to Parallel Machines
• News from the online traveling repairman.
• On randomization in on-line computation.
• On-line dial-a-ride problems under a restricted information model
• On-line single-server dial-a-ride problems
• Randomized algorithms for on-line scheduling problems: How low can't you go?
• Scheduling on identical machines: How good is LPT in an on-line setting?
• Speed is as powerful as clairvoyance
• The online TSP against fair adversaries

Cited in

(19)

• The k-client problem
• On the power of lookahead in on-line server routing problems
• Tight analysis of the lazy algorithm for open online dial-a-ride
• Generalized Online Routing: New Competitive Ratios, Resource Augmentation, and Asymptotic Analyses
• The online \(k\)-server problem with rejection
• New lower bounds for online \(k\)-server routing problems
• Competitive analysis of a dispatch policy for a dynamic multi-period routing problem
• Tight analysis of the lazy algorithm for open online dial-a-ride
• Car-sharing between two locations: online scheduling with flexible advance bookings
• An improved algorithm for open online dial-a-ride
• The online \(k\)-taxi problem
• Exploration of graphs with excluded minors
• An improved online algorithm for the traveling repairperson problem on a line
• Online service with delay
• Online service with delay
• Serving requests with on-line routing
• The Online Transportation Problem: On the Exponential Boost of One Extra Server
• The online \(k\)-server problem with max-distance objective
• Online k-Server Routing Problems

This page was built for publication: Online \(k\)-server routing problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q839628)