Marek Karpinskiy

Approximability of Dense and Sparse Instances of Minimum 2-Connectivity, TSP and Path Problems (2008)

Marek Karpinskiy, Piotr Krystaz

Approximability of Dense and Sparse Instances of Minimum 2-Connectivity, TSP and Path Problems (2008)

Marek Karpinskiy, Piotr Krystaz

On-line Load Balancing for Related Machines 1 (Revised Version) (2008)

Piotr Berman, Moses Charikar, Marek Karpinskiy

We consider the problem of scheduling permanent jobs on related machinesin an on-line fashion. We design a new algorithm that achievesthe competitive ratio for the deterministic version,...