Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

11-02-2020 | Issue 2/2020

Journal of Scheduling 2/2020

Broadcasting a file in a communication network

Journal:
Journal of Scheduling > Issue 2/2020
Authors:
Kai-Simon Goetzmann, Tobias Harks, Max Klimm
Important notes
The results of Section 3 of this paper appeared as an extended abstract in Proceedings of the 22nd International Symposium on Algorithms and Computation (Goetzmann et al. 2011).
The research of Kai-Simon Goetzmann was supported by the Deutsche Forschungsgemeinschaft within the research training group “Methods for Discrete Structures” (GRK 1408).
The research of Max Klimm was carried out in the framework of Matheon supported by Einstein Foundation Berlin (MI-8).

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Abstract

We study the problem of distributing a file, initially located at a server, among a set of n nodes. The file is divided into \(m\ge 1\) equally sized packets. After downloading a packet, nodes can upload it to other nodes, possibly to multiple nodes in parallel. Each node, however, may receive each packet from a single source node only. The upload and download rates between nodes are constrained by node- and server-specific upload and download capacities. The objective is to minimize the makespan. This problem has been proposed and analyzed first by Mundinger et al. (J Sched 11:105–120, 2008. https://​doi.​org/​10.​1007/​s10951-007-0017-9) under the assumption that uploads obey the fair sharing principle, that is, concurrent upload rates from a common source are equal at any point in time. Under this assumption, the authors devised an optimal polynomial time algorithm for the case where the upload capacity of the server and the nodes’ upload and download capacities are all equal. In this work, we drop the fair sharing assumption and derive an exact polynomial time algorithm for the case when upload and download capacities per node and among nodes are equal. We further show that the problem becomes strongly NP-hard for equal upload and download capacities per node that may differ among nodes, even for a single packet. For this case, we devise a polynomial time \(\smash {(1+2\sqrt{2})}\)-approximation algorithm. Finally, we devise two polynomial time algorithms with approximation guarantees of 5 and \(2 + \lceil \log _2 \lceil n/m\rceil \rceil /m\), respectively, for the general case of m packets.

Please log in to get access to this content

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Testen Sie jetzt 30 Tage kostenlos.

Literature
About this article

Other articles of this Issue 2/2020

Journal of Scheduling 2/2020 Go to the issue

Premium Partner

    Image Credits