Pavlos S. Efraimidis, Paul Spirakis

The problem of Scheduling $n$ Independent Jobs

on $m$ Unrelated Parallel Machines, when $m$

is fixed, is considered. The standard problem

of minimizing the makespan of the schedule

(SUM) and the bicriteria problem of scheduling

with bounded makespan and cost (SUMC), are

addressed, and randomized fully linear time

more >>>

Andreas Jakoby, Maciej Liskiewicz, RĂ¼diger Reischuk

A model for parallel and distributed programs, the dynamic process graph (DPG),

is investigated under graph-theoretic and complexity aspects.

Such graphs embed constructors for parallel programs,

synchronization mechanisms as well as conditional branches.

They are capable of representing all possible executions of a

parallel or distributed program ...
more >>>

Chandra Chekuri, Sanjeev Khanna

We present the first approximation schemes for minimizing weighted flow time

on a single machine with preemption. Our first result is an algorithm that

computes a $(1+\eps)$-approximate solution for any instance of weighted flow

time in $O(n^{O(\ln W \ln P/\eps^3)})$ time; here $P$ is the ratio ...
more >>>

Andreas Jakoby, Maciej Liskiewicz, RĂ¼diger Reischuk

In parallel and distributed computing scheduling low level tasks

on the available hardware is a fundamental problem.

Traditionally, one has assumed that the set of tasks to be executed

is known beforehand.

Then the scheduling constraints are given by a precedence graph.

Nodes represent the elementary tasks ...
more >>>

Alexis Kaporis, Efpraxia Politopoulou, Paul Spirakis

Consider a system M of parallel machines, each with a strictly increasing and differentiable load dependent latency function. The users of such a system are of infinite number and act selfishly, routing their infinitesimally small portion of the total flow r they control, to machines of currently minimum delay. It ... more >>>

Sai Sandeep

Multidimensional packing problems generalize the classical packing problems such as Bin Packing, Multiprocessor Scheduling by allowing the jobs to be $d$-dimensional vectors. While the approximability of the scalar problems is well understood, there has been a significant gap between the approximation algorithms and the hardness results for the multidimensional variants. ... more >>>