LP Relaxations for Reordering Buffer Management
summary
LPs model the output as fractional batches and the dual as Y and Z prices; rounding one natural LP doubles cost but needs a buffer of size about 2K, yielding an offline O(log K) integrality gap. An online continuous-penalty algorithm is analyzed by dual-fitting and a primal‑dual scheme with resource augmentation, giving deterministic O(K / log log K) and randomized Θ(log log K) competitive bounds; constant‑factor offline approximations and better weighted/metric LPs remain open.
AI-written summary · about