Hitting-Set IP Relaxation and Tiled Interval Cover for Paging with Time Windows and Delays
Algorithms AIMech:HittingSetIPAndTiledIntervalCoverOnlinePagingWithTimeWindowsAndDelays DRAFT
Aliases: PageTW and PageD Hitting-Set IP Caching Algorithm, Right-and-Double-Extension Hitting-Set LP for Caching with Deadlines, Gupta-Kumar-Panigrahi Online Paging with Time Windows and Delays
An online and offline approximation framework for weighted paging with request time windows (PageTW) and monotone delay penalties (PageD) on a cache of size k over n pages that replaces the Omega(k)-integrality-gap interval-packing LP with a Hitting-Set Integer Program enforcing right-extension constraints Rext(I, t) = [s(I), ..., max(t, e(I))] over k+1 distinct pages and double-extension constraints Dext(I, t) = [min(s(I_t), s(I)), ..., t] over k distinct non-critical pages, solves the compactified constraints via Tiled Interval Cover (TiledIC/TiledICEx) and non-nested net extension, and converts online hitting-set solutions into feasible cache schedules via Hall-set weight thresholding and earliest-deadline-first charging forests to achieve O(log k log n)-competitive online and O(1)-approximate offline bounds.
Identity Notes & Concept Scope
No AIO class represents online primal-dual hitting-set LP/IP relaxations for paging with time windows and delays; MachineLearningTask (AIO:MachineLearningTask) is the closest broad match covering online sequential decision-making and optimization tasks.
Claims & Grounded Evidence
4 Claims
Mechanism
#right-and-double-extension-hitting-set-ip-and-tiled-interval-cover-reduction
Whereas the natural interval-packing LP relaxation for PageTW has an Omega(k) integrality gap (Theorem B.1), the Hitting-Set IP with right extensions Rext(I, t) = [s(I), ..., max(t, e(I))] (Constraint R1/R2p) and double extensions Dext(I, t) = [min(s(I_t), s(I)), ..., t] (Constraint D1/D3p) reduces to Tiled Interval Cover (TiledIC, which is totally unimodular with integrality gap 1) and TiledICEx (integrality gap at most 2, Lemma D.1) plus two applications of the non-nested net Extension Theorem (Theorem 5.12), yielding a constant O(1) integrality gap and O(log k)-competitive online IP solution (Corollary 5.15).
Mechanism
#hall-set-threshold-and-charging-forest-online-schedule-conversion
Given a past-preserving, sparse online hitting-set solution A^*_t, ConvertOnline (Algorithms 1-2) uses Hall's marriage theorem (Lemma 3.4) to select a resident hit page p^* in Z^* satisfying w(U^circ_{<= 2 w(p^*)}) <= 2 w(Z^*_{<= w(p^*)}) and bounds overlapping-interval evictions via a weight-class charging forest F = (T, E) (Claims 3.8-3.13), converting an alpha-competitive online hitting-set solution into an O(alpha log n)-competitive cache schedule (Theorem 3.1) and an O(alpha)-approximate offline schedule via reverse-delete pruning (Algorithm 3, Theorem 4.1).
Application
#deadline-io-scheduling-and-video-streaming-delayed-caching-application
By decomposing each general monotone delay request (p, t, F) into an ensemble of deadline intervals [t, t'] with incremental penalties F(t'+1) - F(t') (Section 6, Theorem 6.1), the framework provides O(log k log n)-competitive online and O(1)-approximate offline caching schedules for deadline-aware I/O scheduling and video-on-demand segment caching.
Limitation
#clairvoyant-deadline-knowledge-and-extra-log-n-online-conversion-limitation
The O(log k log n)-competitive online bound for PageTW requires the clairvoyant setting in which a request's deadline e(I) is revealed at arrival time s(I) (used to sort active requests in earliest-deadline-first order in Algorithm 2, line 16) and incurs an extra O(log n) factor over the O(log k) classical weighted paging bound when converting overlapping request intervals across weight classes (Section 2, p. 6; Section 3.2, p. 12-16).
⚠️ Curated Limitations & Negative Results
- The O(log k log n)-competitive online bound for PageTW requires the clairvoyant setting in which a request's deadline e(I) is revealed at arrival time s(I) (used to sort active requests in earliest-deadline-first order in Algorithm 2, line 16) and incurs an extra O(log n) factor over the O(log k) classical weighted paging bound when converting overlapping request intervals across weight classes (Section 2, p. 6; Section 3.2, p. 12-16).
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:MachineLearningTask
Machine Learning Task
|
broad_match | Online primal-dual LP rounding and competitive online caching with deadlines/delays is a sequential online optimization and decision-making framework. |
Evidence Sources & Primary Literature
3 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
r835-primary-pdf
|
Anupam Gupta, Amit Kumar, Debmalya Panigrahi
|
primary paper
full_text
|
ID: https://arxiv.org/abs/2006.09665
sha256:0c3d8484b197…
|
r835-arxiv-abs
|
Anupam Gupta, Amit Kumar, Debmalya Panigrahi
|
primary paper
abstract_only
|
ID: https://arxiv.org/abs/2006.09665
sha256:fa2845c5c8f1…
|
r835-metadata-cr
|
Anupam Gupta, Amit Kumar, Debmalya Panigrahi
|
primary paper
abstract_only
|
ID: https://arxiv.org/abs/2006.09665
sha256:777a7b87e1ef…
|
Ontology & Grounding Topology
Open in interactive network graph →Curation Provenance
Curator: Antigravity
Method: ai_assisted
Model: Gemini
Created: 2026-10-19T15:18:00Z
Updated: 2026-10-19T15:18:00Z
Explore across X-Mech
Related computational & biological Mechs:
Embedding Map
Network Graph
ProteinTraitsMech (ESM-2 pLM)
DUFMech (Domain pLM)
TraitMech
CultureMech
All 14 X-Mech Repositories