The present chapter reviews the work on the broadcasting problem of N data items over K wireless channels, under the assumptions of skewed data allocation to channels and flat data scheduling per channel. Both the uniform and nonuniform length cases are surveyed showing their exact and heuristic solutions, respectively. For the case of data items with uniform lengths, four exact polynomial time algorithms are presented, all based on dynamic programming. The first algorithm, called DP, takes O(K N^2) time, whereas the second algorithm, called Dichotomic is faster as it runs in O(K N log N) time. The third algorithm is designed for the specific case of K = 2. Although it requires O(N log N) time, and hence it is asymptotically not faster than Dichotomic, it exploits a specific characterization of the optimal solution that we also use in developing the heuristics for the nonuniform case. Finally, the fourth algorithm, called Smawk-AED has been very recently presented and it takes O(NK) time. This algorithm matches the trivial lower bound for the time complexity of any dynamic programming algorithm for the K-uniform allocation problem that solves all the NK subproblems of allocating a prefix of the items {1, . . . , n} to k channels, 1 ≤ n ≤ N, 1 ≤ k ≤ K. For the case of data items with nonuniform lengths, the problem is NP-hard when K = 2, and strong NP-hard for arbitrary K. In this latter case, the Optimal algorithm is reviewed. It requires O(z K N^2) time, where z is the maximum data length, and reduces to the DP algorithm when z = 1. As algorithm Optimal can solve only small instances in a reasonable time, three heuristics are described, all having an O(N(K + log N)) time complexity. All the three heuristics are then tested on benchmarks whose popularities are characterized by Zipf distributions. The experimental tests reveal that one heuristic, called Dlinear, finds optimal solutions almost always, requiring reasonable running times.

Alan Albert Bertossi, M.C.P. (2018). Data broadcast on multiple wireless channels – Exact and time-optimal solutions for uniform data and heuristics for non-uniform data. Boca Raton : Chapman and Hall / CRC Press.

Data broadcast on multiple wireless channels – Exact and time-optimal solutions for uniform data and heuristics for non-uniform data

Alan Albert Bertossi;
2018

Abstract

The present chapter reviews the work on the broadcasting problem of N data items over K wireless channels, under the assumptions of skewed data allocation to channels and flat data scheduling per channel. Both the uniform and nonuniform length cases are surveyed showing their exact and heuristic solutions, respectively. For the case of data items with uniform lengths, four exact polynomial time algorithms are presented, all based on dynamic programming. The first algorithm, called DP, takes O(K N^2) time, whereas the second algorithm, called Dichotomic is faster as it runs in O(K N log N) time. The third algorithm is designed for the specific case of K = 2. Although it requires O(N log N) time, and hence it is asymptotically not faster than Dichotomic, it exploits a specific characterization of the optimal solution that we also use in developing the heuristics for the nonuniform case. Finally, the fourth algorithm, called Smawk-AED has been very recently presented and it takes O(NK) time. This algorithm matches the trivial lower bound for the time complexity of any dynamic programming algorithm for the K-uniform allocation problem that solves all the NK subproblems of allocating a prefix of the items {1, . . . , n} to k channels, 1 ≤ n ≤ N, 1 ≤ k ≤ K. For the case of data items with nonuniform lengths, the problem is NP-hard when K = 2, and strong NP-hard for arbitrary K. In this latter case, the Optimal algorithm is reviewed. It requires O(z K N^2) time, where z is the maximum data length, and reduces to the DP algorithm when z = 1. As algorithm Optimal can solve only small instances in a reasonable time, three heuristics are described, all having an O(N(K + log N)) time complexity. All the three heuristics are then tested on benchmarks whose popularities are characterized by Zipf distributions. The experimental tests reveal that one heuristic, called Dlinear, finds optimal solutions almost always, requiring reasonable running times.
2018
Handbook of Approximation Algorithms and Metaheuristics – Contemporary and Emerging Applications - Volume 2
483
504
Alan Albert Bertossi, M.C.P. (2018). Data broadcast on multiple wireless channels – Exact and time-optimal solutions for uniform data and heuristics for non-uniform data. Boca Raton : Chapman and Hall / CRC Press.
Alan Albert Bertossi, Maria Cristina Pinotti, Romeo Rizzi
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/646866
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact