Capacitated Line Aggregation with Maximum Delay

Overview & Synopsis

We study capacitated line aggregation with per-batch maximum delay. Requests arrive over time at locations on a rooted half-line and are served in instantaneous batches of at most $k$ requests. Each batch pays the distance to its farthest request plus the waiting time of its oldest request. The objective is to minimize the total cost. We give a deterministic online algorithm with competitive ratio $36+12\sqrt3$. The algorithm uses a Next Fit idea along paths of nested time intervals: it assigns a new group to an existing batch when a path-load test permits, and opens a new batch otherwise. The path load controls both capacity and the cost of opening new batches. Randomizing the common scale improves the expected competitive ratio to $(18+6\sqrt3)/\ln2$ against an oblivious adversary. Both guarantees extend to arbitrary indivisible request sizes. We also study capacitated LAD in the learning-augmented model. Advice revealed at its service times allows $(1+ε)$-consistency against every complete feasible advice schedule and $O(ε^{-2})$-robustness. The analysis charges repeated switches to successive decreases in the remaining advice cost.