Skip to main content
Erschienen in: Distributed Computing 1/2019

30.12.2017

Distributed approximation of k-service assignment

verfasst von: Magnús M. Halldórsson, Sven Köhler, Dror Rawitz

Erschienen in: Distributed Computing | Ausgabe 1/2019

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We consider the k-Service Assignment problem (\(k\)-SA). The input consists of a network that contains servers and clients. Associated with each client is a demand and a profit. In addition, each client c has a service requirement https://static-content.springer.com/image/art%3A10.1007%2Fs00446-017-0321-3/MediaObjects/446_2017_321_IEq2_HTML.gif , where \(\kappa (c)\) is a positive integer. A client c is satisfied only if its demand is handled by exactly \(\kappa (c)\) neighboring servers. The objective is to maximize the total profit of satisfied clients, while obeying the given capacity limits of the servers. We focus here on the more challenging case of hard constraints, where no profit is granted for partially satisfied clients. This models, e.g., when a client wants, for reasons of fault tolerance, a file to be stored at \(\kappa (c)\) or more nearby servers. Other motivations from the literature include resource allocation in 4G cellular networks and machine scheduling on related machines with assignment restrictions. In the r-restricted version of \(k\)-SA, no client requires more than an r-fraction of the capacity of any adjacent server. We present a (centralized) polynomial-time https://static-content.springer.com/image/art%3A10.1007%2Fs00446-017-0321-3/MediaObjects/446_2017_321_IEq7_HTML.gif -approximation algorithm for r-restricted \(k\)-SA. A variant of this algorithm achieves an approximation ratio of https://static-content.springer.com/image/art%3A10.1007%2Fs00446-017-0321-3/MediaObjects/446_2017_321_IEq9_HTML.gif when given a resource augmentation factor of \(1+r\). We use the latter result to present a https://static-content.springer.com/image/art%3A10.1007%2Fs00446-017-0321-3/MediaObjects/446_2017_321_IEq11_HTML.gif -approximation algorithm for \(k\)-SA. In the distributed setting, we present: (i) a https://static-content.springer.com/image/art%3A10.1007%2Fs00446-017-0321-3/MediaObjects/446_2017_321_IEq13_HTML.gif -approximation algorithm for r-restricted \(k\)-SA, (ii) a https://static-content.springer.com/image/art%3A10.1007%2Fs00446-017-0321-3/MediaObjects/446_2017_321_IEq15_HTML.gif -approximation algorithm that uses a resource augmentation factor of \(1+r\) for r-restricted \(k\)-SA, both for any constant \(\varepsilon >0\), and (iii) an https://static-content.springer.com/image/art%3A10.1007%2Fs00446-017-0321-3/MediaObjects/446_2017_321_IEq19_HTML.gif -approximation algorithm for \(k\)-SA (in expectation). The three distributed algorithms run in \(O(k^2 \varepsilon ^{-2} \log ^3 n)\) synchronous rounds (with high probability). In particular, this yields the first distributed https://static-content.springer.com/image/art%3A10.1007%2Fs00446-017-0321-3/MediaObjects/446_2017_321_IEq22_HTML.gif -approximation of \(1\)-SA.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

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

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

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




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Amzallag, D., Bar-Yehuda, R., Raz, D., Scalosub, G.: Cell selection in 4G cellular networks. IEEE Trans. Mobile Comput. 12(7), 1443–1455 (2013)CrossRef Amzallag, D., Bar-Yehuda, R., Raz, D., Scalosub, G.: Cell selection in 4G cellular networks. IEEE Trans. Mobile Comput. 12(7), 1443–1455 (2013)CrossRef
3.
Zurück zum Zitat Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J., Schieber, B.: A unified approach to approximating resource allocation and scheduling. J. ACM 48(5), 1069–1090 (2001)MathSciNetCrossRefMATH Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J., Schieber, B.: A unified approach to approximating resource allocation and scheduling. J. ACM 48(5), 1069–1090 (2001)MathSciNetCrossRefMATH
4.
Zurück zum Zitat Bar-Yehuda, R., Bendel, K., Freund, A., Rawitz, D.: Local ratio: a unified framework for approximation algorithms. ACM Comput. Surv. 36(4), 422–463 (2004)CrossRef Bar-Yehuda, R., Bendel, K., Freund, A., Rawitz, D.: Local ratio: a unified framework for approximation algorithms. ACM Comput. Surv. 36(4), 422–463 (2004)CrossRef
5.
Zurück zum Zitat Bar-Yehuda, R., Even, S.: A local-ratio theorem for approximating the weighted vertex cover problem. Ann. Discret. Math. 25, 27–46 (1985)MathSciNetMATH Bar-Yehuda, R., Even, S.: A local-ratio theorem for approximating the weighted vertex cover problem. Ann. Discret. Math. 25, 27–46 (1985)MathSciNetMATH
7.
Zurück zum Zitat Chekuri, C., Khanna, S.: A polynomial time approximation scheme for the multiple knapsack problem. SIAM J. Comput. 35(3), 713–728 (2005)MathSciNetCrossRefMATH Chekuri, C., Khanna, S.: A polynomial time approximation scheme for the multiple knapsack problem. SIAM J. Comput. 35(3), 713–728 (2005)MathSciNetCrossRefMATH
8.
Zurück zum Zitat Cohen, R., Grebla, G.: Joint scheduling and fast cell selection in OFDMA wireless networks. IEEE/ACM Trans. Netw. 23(1), 114–125 (2015)CrossRef Cohen, R., Grebla, G.: Joint scheduling and fast cell selection in OFDMA wireless networks. IEEE/ACM Trans. Netw. 23(1), 114–125 (2015)CrossRef
9.
Zurück zum Zitat Cohen, R., Katzir, L., Raz, D.: An efficient approximation for the generalized assignment problem. Inf. Process. Lett. 100(4), 162–166 (2006)MathSciNetCrossRefMATH Cohen, R., Katzir, L., Raz, D.: An efficient approximation for the generalized assignment problem. Inf. Process. Lett. 100(4), 162–166 (2006)MathSciNetCrossRefMATH
10.
Zurück zum Zitat Dawande, M., Kalagnanam, J., Keskinocak, P., Salman, F.S., Ravi, R.: Approximation algorithms for the multiple knapsack problem with assignment restrictions. J. Comb. Optim. 4(2), 171–186 (2000)MathSciNetCrossRefMATH Dawande, M., Kalagnanam, J., Keskinocak, P., Salman, F.S., Ravi, R.: Approximation algorithms for the multiple knapsack problem with assignment restrictions. J. Comb. Optim. 4(2), 171–186 (2000)MathSciNetCrossRefMATH
11.
Zurück zum Zitat Emek, Y., Halldórsson, M.M., Mansour, Y., Patt-Shamir, B., Radhakrishnan, J., Rawitz, D.: Online set packing. SIAM J. Comput. 41(4), 728–746 (2012)MathSciNetCrossRefMATH Emek, Y., Halldórsson, M.M., Mansour, Y., Patt-Shamir, B., Radhakrishnan, J., Rawitz, D.: Online set packing. SIAM J. Comput. 41(4), 728–746 (2012)MathSciNetCrossRefMATH
12.
13.
Zurück zum Zitat Feige, U., Vondrák, J.: Approximation algorithms for allocation problems: improving the factor of 1-1/e. In: 47th IEEE Annual Symposium on Foundations of Computer Science, pp. 667–676 (2006) Feige, U., Vondrák, J.: Approximation algorithms for allocation problems: improving the factor of 1-1/e. In: 47th IEEE Annual Symposium on Foundations of Computer Science, pp. 667–676 (2006)
14.
Zurück zum Zitat Fleischer, L., Goemans, M.X., Mirrokni, V.S., Sviridenko, M.: Tight approximation algorithms for maximum general assignment problems. In: 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 611–620 (2006) Fleischer, L., Goemans, M.X., Mirrokni, V.S., Sviridenko, M.: Tight approximation algorithms for maximum general assignment problems. In: 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 611–620 (2006)
15.
Zurück zum Zitat Frieze, A.M., Clarke, M.R.B.: Approximation algorithms for the \(m\)-dimensional \(0-1\) knapsack problem: worst-case and probabilistic analyses. Eur. J. Oper. Res. 15, 100–109 (1984)MathSciNetCrossRefMATH Frieze, A.M., Clarke, M.R.B.: Approximation algorithms for the \(m\)-dimensional \(0-1\) knapsack problem: worst-case and probabilistic analyses. Eur. J. Oper. Res. 15, 100–109 (1984)MathSciNetCrossRefMATH
16.
Zurück zum Zitat Gurewitz, O., Sandomirsky, Y., Scalosub, G.: Cellular multi-coverage with non-uniform rates. In: INFOCOM, pp. 1330–1338 (2014) Gurewitz, O., Sandomirsky, Y., Scalosub, G.: Cellular multi-coverage with non-uniform rates. In: INFOCOM, pp. 1330–1338 (2014)
17.
Zurück zum Zitat Halldórsson, M.M., Köhler, S., Patt-Shamir, B., Rawitz, D.: Distributed backup placement in networks. In: 27th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 274–283 (2015) Halldórsson, M.M., Köhler, S., Patt-Shamir, B., Rawitz, D.: Distributed backup placement in networks. In: 27th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 274–283 (2015)
18.
19.
Zurück zum Zitat Hazan, E., Safra, S., Schwartz, O.: On the complexity of approximating \(k\)-set packing. Comput. Complex. 15(1), 20–39 (2006)MathSciNetCrossRefMATH Hazan, E., Safra, S., Schwartz, O.: On the complexity of approximating \(k\)-set packing. Comput. Complex. 15(1), 20–39 (2006)MathSciNetCrossRefMATH
20.
Zurück zum Zitat Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22(4), 463–468 (1975)MathSciNetCrossRefMATH Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22(4), 463–468 (1975)MathSciNetCrossRefMATH
21.
22.
Zurück zum Zitat Magazine, M.J., Chern, M.S.: A note on approximation schemes for multidimensional knapsack problems. Math. Oper. Res. 9(2), 244–247 (1984)MathSciNetCrossRefMATH Magazine, M.J., Chern, M.S.: A note on approximation schemes for multidimensional knapsack problems. Math. Oper. Res. 9(2), 244–247 (1984)MathSciNetCrossRefMATH
23.
Zurück zum Zitat Patt-Shamir, B., Rawitz, D., Scalosub, G.: Distributed approximation of cellular coverage. J. Parallel Distrib. Comput. 72(3), 402–408 (2012)CrossRefMATH Patt-Shamir, B., Rawitz, D., Scalosub, G.: Distributed approximation of cellular coverage. J. Parallel Distrib. Comput. 72(3), 402–408 (2012)CrossRefMATH
24.
Zurück zum Zitat Peleg, D.: Distributed computing: a locality-sensitive approach. Society for Industrial and Applied Mathematics, Philadelphia (2000) Peleg, D.: Distributed computing: a locality-sensitive approach. Society for Industrial and Applied Mathematics, Philadelphia (2000)
25.
Zurück zum Zitat Raghavan, P., Thompson, C.D.: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7(4), 365–374 (1987)MathSciNetCrossRefMATH Raghavan, P., Thompson, C.D.: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7(4), 365–374 (1987)MathSciNetCrossRefMATH
26.
Zurück zum Zitat Rawitz, D., Voloshin, A.: Flexible cell selection in cellular networks. In: 12th International Symposium on Algorithms and Experiments for Wireless Sensor Networks. LNCS, vol. 10050, pp. 112–128 (2016) Rawitz, D., Voloshin, A.: Flexible cell selection in cellular networks. In: 12th International Symposium on Algorithms and Experiments for Wireless Sensor Networks. LNCS, vol. 10050, pp. 112–128 (2016)
28.
Zurück zum Zitat Shmoys, D.B., Tardos, É.: An approximation algorithm for the generalized assignment problem. Math. Program. 62, 461–474 (1993)MathSciNetCrossRefMATH Shmoys, D.B., Tardos, É.: An approximation algorithm for the generalized assignment problem. Math. Program. 62, 461–474 (1993)MathSciNetCrossRefMATH
29.
Zurück zum Zitat Srinivasan, A.: Improved approximation guarantees for packing and covering integer programs. SIAM J. Comput. 29(2), 648–670 (1999)MathSciNetCrossRefMATH Srinivasan, A.: Improved approximation guarantees for packing and covering integer programs. SIAM J. Comput. 29(2), 648–670 (1999)MathSciNetCrossRefMATH
Metadaten
Titel
Distributed approximation of k-service assignment
verfasst von
Magnús M. Halldórsson
Sven Köhler
Dror Rawitz
Publikationsdatum
30.12.2017
Verlag
Springer Berlin Heidelberg
Erschienen in
Distributed Computing / Ausgabe 1/2019
Print ISSN: 0178-2770
Elektronische ISSN: 1432-0452
DOI
https://doi.org/10.1007/s00446-017-0321-3

Weitere Artikel der Ausgabe 1/2019

Distributed Computing 1/2019 Zur Ausgabe