Online Algorithm

An online algorithm receives its input as a sequence or stream, processing each piece one at a time. It must make a decision or produce an output for each input item before seeing the next. This is fundamental to real-time systems like dynamic routing, where tasks (e.g., delivery requests) arrive continuously and must be assigned immediately.

• Example: A food delivery app assigning each new order to a driver as it arrives, without knowing future order locations or times.

Decisions made by an online algorithm are typically final or costly to reverse. Once an agent is assigned a route or a resource is allocated, changing that assignment incurs a switching cost or causes significant disruption. This characteristic necessitates careful, often conservative, decision-making to avoid poor long-term outcomes.

• Contrast: An offline algorithm can backtrack and re-optimize the entire plan after seeing all data.

The performance of an online algorithm is measured using competitive analysis. It compares the algorithm's solution cost to the optimal offline solution cost (calculated with full future knowledge).

If for all possible input sequences, the online algorithm's cost is at most c times the optimal offline cost plus a constant, the algorithm is c-competitive. A lower competitive ratio (c) indicates better worst-case performance.

• Formula: Cost_online(σ) ≤ c * Cost_optimal(σ) + α for all sequences σ.

The defining constraint is the absence of clairvoyance. The algorithm has no information about future inputs, their timing, or their properties. This models real-world uncertainty. Performance hinges on the algorithm's strategy for handling this uncertainty, often using:

• Conservative strategies that preserve flexibility.
• Aggressive strategies that optimize for immediate gain.
• Predictive models that estimate future inputs, though these are heuristic and not guaranteed.

Online algorithms must produce decisions within a strict time constraint, often immediately upon receiving an input item. The computational complexity per decision must be low, typically O(log n) or O(1), to ensure the system remains responsive to a high-frequency stream of events.

This excludes complex, batch-style optimization from consideration for the core decision loop.

In heterogeneous fleet orchestration, online algorithms are the core of real-time replanning engines and dynamic task allocators. They handle:

• New task insertion: Assigning a high-priority job to the best-suited agent immediately.
• Agent failure: Re-routing other agents to cover the failed agent's tasks.
• Traffic delay: Recalculating paths for affected agents in real-time.

Classic theoretical models include the Online Transportation Problem and the k-Server Problem, which abstract dynamic resource allocation.

In heterogeneous fleet orchestration, online algorithms process new delivery requests, traffic updates, and agent status changes in real-time. They must irrevocably assign tasks and plan routes without knowing future orders. This is a canonical application of the Online Vehicle Routing Problem (OVRP), where the goal is to minimize total travel distance or maximize on-time deliveries despite an unknown stream of future pickups and drop-offs.

Operating system schedulers are classic online algorithms. They must allocate the CPU to incoming processes without knowledge of future job arrivals or runtimes. Algorithms like Shortest Remaining Time First (SRTF) or Earliest Deadline First (EDF) make immediate decisions that impact system responsiveness and throughput. The competitive ratio is a key metric, comparing the online scheduler's performance against an optimal offline clairvoyant scheduler.

High-frequency trading platforms and stock exchanges use online algorithms to match buy and sell orders as they arrive. The algorithm must immediately decide whether to execute an incoming order at the current best price or place it in an order book, without knowing the composition of future orders. This directly applies the online bipartite matching problem, where the goal is to maximize total value matched in a stream of requests.

Managing a finite cache (e.g., CPU cache, web CDN) is a foundational online problem. When a requested item is not in the cache (a miss), the algorithm must evict an existing item to make space, without knowing future requests. Well-known strategies like Least Recently Used (LRU) and First-In-First-Out (FIFO) are online heuristics. The competitive analysis of paging algorithms, like the proven performance bounds of LRU, is a cornerstone of online algorithm theory.

When a user loads a webpage, an auction for ad space occurs in milliseconds. Each advertiser's bidding algorithm receives user context and must submit a bid without knowing the bids of other participants or details of the next impression. This is an online selection problem under budget constraints. Algorithms must pace spending across a potentially unknown sequence of opportunities to maximize conversions or clicks.

This abstract, theoretical problem models many real-world scenarios like request routing in a server farm or mobile agent patrol. k servers (or agents) exist in a metric space. Requests arrive online at points in the space, and an algorithm must immediately select a server to move and serve the request, minimizing total movement cost. While theoretically complex, it directly informs the design of algorithms for dynamic resource allocation and load balancing in unpredictable environments.

An offline algorithm has complete knowledge of the entire input sequence from the start, allowing it to compute an optimal solution with full foresight. This contrasts with online algorithms, which must make irrevocable decisions without future knowledge.

• Key Difference: Possesses the entire problem instance upfront.
• Performance Benchmark: The optimal offline solution is used to measure the competitive ratio of an online algorithm.
• Example: Computing the absolute shortest path for a day's deliveries after all orders are known, versus routing vehicles as orders arrive.

The competitive ratio is the primary theoretical performance measure for an online algorithm. It quantifies the worst-case ratio between the cost (or value) of the online algorithm's solution and the cost of the optimal offline solution that knows the future.

• Formula: For a minimization problem, if ALG(I) is the online algorithm's cost and OPT(I) is the optimal offline cost on input sequence I, the competitive ratio is sup over all I of [ALG(I) / OPT(I)].
• Interpretation: A ratio of 2 means the online algorithm is never worse than twice the optimal offline solution, even in an adversarial scenario.
• Significance: Provides a rigorous, data-independent guarantee for dynamic systems where future inputs are unknown.

Dynamic replanning is the practical capability of a system to modify or generate a new plan in real-time as the environment changes. It is the engineering implementation of online algorithmic principles.

• Core Mechanism: Continuously monitors the world state (e.g., new high-priority tasks, agent breakdowns, blocked paths) and triggers a re-optimization.
• Algorithms: Often uses incremental search algorithms like D Lite* or Lifelong Planning A (LPA)** to update paths efficiently without recomputing from scratch.
• Use Case: In fleet orchestration, a robot's route is dynamically replanned when a human-operated forklift unexpectedly blocks its planned corridor.

A greedy algorithm makes a series of choices, each of which looks best at the moment (locally optimal), without regard for the overall future consequences. Many effective online algorithms employ greedy heuristics due to their low computational overhead.

• Online Nature: By definition, a greedy algorithm processes input sequentially and makes irrevocable decisions, fitting the online paradigm.
• Trade-off: Often simple and fast but may not provide strong competitive guarantees. Example: Always assigning the nearest available robot to a new task.
• Analysis: Competitive analysis is frequently used to evaluate the worst-case performance of greedy online strategies.

A real-time system is one where the correctness of the system depends not only on the logical result of computation but also on the time at which the results are produced. Online algorithms are a critical component of the decision-making layer in such systems.

• Hard vs. Soft Deadlines: Must meet absolute deadlines (hard) or strive to meet them (soft). Online algorithms for routing often incorporate Earliest Deadline First (EDF) principles.
• Determinism: Requires predictable, bounded execution times for algorithms, influencing the design of online solvers.
• Context: In heterogeneous fleets, the orchestration platform is a real-time system that uses online algorithms to make scheduling decisions within strict latency bounds.

Adversarial analysis is a framework for evaluating online algorithms under the assumption that future inputs are chosen by an opponent to maximize the algorithm's cost relative to the optimal solution. It underpins competitive analysis.

• Philosophy: "Prepare for the worst." It provides robust guarantees that hold even under unexpected or malicious input sequences.
• Design Impact: Leads to the creation of conservative, randomized, or memory-enhanced algorithms that perform well against an adversary.
• Example: An online task assignment algorithm is analyzed against an adversary that generates new high-priority tasks precisely when all critical agents are occupied.