Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SCHEDULING:
Reports tagged with Scheduling:
TR00-007 | 14th December 1999
Pavlos S. Efraimidis, Paul Spirakis

#### Randomized Approximation Schemes for Scheduling Unrelated Parallel Machines

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 >>>

TR01-038 | 14th May 2001
Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk

#### Approximating Schedules for Dynamic Graphs Efficiently

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 >>>

TR01-065 | 10th August 2001
Chandra Chekuri, Sanjeev Khanna

#### Approximation Schemes for Preemptive Weighted Flow Time

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 >>>

TR01-090 | 28th November 2001
Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk

#### Dynamic Process Graphs and the Complexity of Scheduling

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 >>>

TR05-056 | 25th April 2005
Alexis Kaporis, Efpraxia Politopoulou, Paul Spirakis

#### The Price of Optimum in Stackelberg Games

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 >>>

TR21-007 | 14th January 2021
Sai Sandeep

#### Almost Optimal Inapproximability of Multidimensional Packing Problems

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 >>>

ISSN 1433-8092 | Imprint