Convex Quadratic Programming Relaxations for Network Scheduling Problems
dc.contributor.author | Skutella, Martin | |
dc.date.accessioned | 2021-12-17T10:16:58Z | |
dc.date.available | 2021-12-17T10:16:58Z | |
dc.date.issued | 1999 | |
dc.description.abstract | 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. | en |
dc.identifier.issn | 2197-8085 | |
dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15942 | |
dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14715 | |
dc.language.iso | en | en |
dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
dc.subject.ddc | 510 Mathematik | en |
dc.subject.other | approximation algorithm | en |
dc.subject.other | randomized algorithm | en |
dc.subject.other | convex quadratic program | en |
dc.subject.other | scheduling | en |
dc.title | Convex Quadratic Programming Relaxations for Network Scheduling Problems | en |
dc.type | Research Paper | en |
dc.type.version | submittedVersion | en |
tub.accessrights.dnb | free | en |
tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
tub.affiliation.institute | Inst. Mathematik | de |
tub.publisher.universityorinstitution | Technische Universität Berlin | en |
tub.series.issuenumber | 1999, 629 | en |
tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |
tub.subject.msc2000 | 90C27 Combinatorial optimization | en |
tub.subject.msc2000 | 68Q25 Analysis of algorithms and problem complexity | en |
tub.subject.msc2000 | 90B35 Scheduling theory, deterministic | en |
tub.subject.msc2000 | 68M20 Performance evaluation; queueing; scheduling | en |
tub.subject.msc2000 | 90C20 Quadratic programming | en |
tub.subject.msc2000 | 90C25 Convex programming | en |