We study online network services that combine pending requests into batches. Each batch pays for its spatial service and for the waiting time of its oldest request. The objective is the sum of these costs over all batches. Thus requests can share both a spatial purchase and one maximum-delay charge. We assume independe...
Classical paging serves every miss immediately. We study paging with per-replacement maximum delay, where loading a pending page costs one movement plus the age of its oldest outstanding request and clears that page's entire episode. Equivalently, the holding rate is the number of pending pages. For cache size $k$, thr...
We study online line aggregation with deadlines, where requests arrive over time on the positive half-line and a service at location $y$ clears all pending requests in $[0,y]$ at cost $y$. In the classical adversarial setting, we propose an $e$-competitive randomized algorithm against an oblivious adversary and prove a...
This work proves strong NP-hardness and rule out absolute approximation factors below three halves unless P equals NP, and obtains an exact stochastic benchmark for Poisson arrivals when every item has half the bin capacity.
Online covering in which each instantaneous service pays its purchase cost and one maximum waiting time, with no effect on future requests is studied, finding an offline consecutive-batch normal form that transfers static approximation guarantees to the offline problem.
The deterministic guarantee matches the known fixed-node lower bound, and the matching randomized lower bound are proved, ensuring that both guarantees are optimal on every nondegenerate rooted tree.
Tian-Han Lu, Run-Tian Ren, Sheng-Cai Liu et al.· 3 citations
This work uses spatial blindness---announced requests whose locations are revealed only when visited---as a stress test: dyadic exploration preserves a constant ratio on a known finite line, while a single hidden request on a star forces a loss linear in its degree.
Tian-Han Lu, Run-Tian Ren, Sheng-Cai Liu et al.· 0 citations
We prove that no randomized integral or fractional algorithm for online vertex cover under general vertex arrivals achieves a competitive ratio strictly below $1+\sqrt{e}/2\approx1.824360635$, even on bipartite graphs and against an oblivious adversary. This improves the previous lower bound of approximately $1.753$. O...
Tian-Han Lu· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.