Online method for grouping requests with capacity and delay limits
Capacitated Line Aggregation with Maximum Delay
Data Structures and Algorithms
Summary
Imagine you have a line of people who need to be served in groups, but each group can only hold a certain number of people, and you want to keep waiting times short. The paper studies how to group these requests arriving one by one in a way that balances travel distance and waiting time. The authors present an online method that decides when to add a new request to an existing group or start a new one, achieving a good balance between efficiency and delay. They also explore how extra information or advice about requests can improve this process even more.
What this means in practice
- •For network schedulers: Schedule data packets arriving over time into limited-size batches minimizing maximum delay and transmission cost for better quality of service.
- •For warehousing operations teams: Organize orders arriving at a dispatch line into batches respecting size limits and reducing wait and travel times to improve delivery efficiency.
Authors
Runtian Ren, Shengcai Liu
Abstract
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.