4 papers · 1 filter
Better Bounds for Incremental Frequency Allocation in Bipartite Graphs
Marek Chrobak, Łukasz Jeż, Jiří Sgall
We study frequency allocation in wireless networks. A wireless network is modeled by an undirected graph, with vertices corresponding to cells. In each vertex we have a certain num…
One to Rule Them All: a General Randomized Algorithm for Buffer Management with Bounded Delay
Łukasz Jeż
We give a memoryless scale-invariant randomized algorithm for the Buffer Management with Bounded Delay problem that is e/(e-1)-competitive against an adaptive adversary, together w…
Online Scheduling of Bounded Length Jobs to Maximize Throughput
Christoph Durr, Lukasz Jez, Nguyen Kim Thang
We consider an online scheduling problem, motivated by the issues present at the joints of networks using ATM and TCP/IP. Namely, IP packets have to broken down to small ATM cells…
Online validation of the pi and pi' failure functions
Pawel Gawrychowski, Artur Jez, Lukasz Jez
Let pi_w denote the failure function of the Morris-Pratt algorithm for a word w. In this paper we study the following problem: given an integer array A[1..n], is there a word w ove…