direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 629-1999

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Convex Quadratic Programming Relaxations for Network Scheduling Problems
In Jaroslav Nesetril (ed.): Algorithms - ESA '99, Lecture Notes in Computer Science 1643, Springer: Berlin, 1999, pp. 127-138, Proceedings of the 7th Annual European Symposium on Algorithms (ESA'99).
primary: 90C27 Combinatorial optimization
secondary: 68Q25 Analysis of algorithms and problem complexity
90B35 Scheduling theory, deterministic
68M20 Performance evaluation; queueing; scheduling
90C20 Quadratic programming
90C25 Convex programming
approximation algorithm, randomized algorithm, convex quadratic program, scheduling
In network scheduling a set of jobs must be scheduled on unrelated parallel processors or machines which are connected by a network. Initially, each job is located on some machine in the network and cannot be started on another machine until sufficient time elapses to allow the job to be transmitted there. This setting has applications, e.g., in distributed multi-processor computing environments and also in operations research; it can be modeled by a standard parallel machine environment with machine-dependent release dates. We consider the objective of minimizing the total weighted completion time.
The main contribution of this paper is a provably good convex quadratic programming relaxation of strongly polynomial size for this problem. Until now, only linear programming relaxations in time- or interval-indexed variables have been studied. Those LP relaxations, however, suffer from a huge number of variables. In particular, the best previously known relaxation is of exponential size and can therefore not be solved exactly in polynomial time. As a result of the convex quadratic programming approach we can give a very simple and easy to analyze randomized 2-approximation algorithm which slightly improves upon the best previously known approximation result. Furthermore, we consider preemptive variants of network scheduling and derive approximation results and results on the power of preemption which improve upon the best previously known results for these settings.
Download as [PDF] [ps.gz]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe