Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Weighted Dissemination of Bundles in Probabilistic Spray and Wait Routing Protocol Read chapter Read first chapter

2020 | OriginalPaper | Chapter

A Comparison of the Effectiveness of Two Novel Clustering-Based Heuristics for the p-Centre Problem

Authors : Mahima Yadav, V. Prem Prakash

Published in: Advances in Data and Information Sciences

Publisher: Springer Singapore

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Given a set of n demand points, the objective of the p-centre problem is to identify a subset of the demand points having p ≪ n nodes (called centres) such that the maximum distance of any demand point to its nearest centre is minimized. The problem is NP-hard and finds application in facility location. This paper presents two novel heuristics for the p-centre problem that requires O(n3) time. One of these is a deterministic heuristic that uses a minimum spanning tree-based clustering approach, and the other is a randomized heuristic that uses greedy clustering. Bounds on the computational time requirements of both heuristics are proved. The relative performance of the two heuristics is evaluated in the course of several computational experiments on a wide range of benchmark problems used in the literature for the p-centre problem.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Standard Library Tool Set for Rough Set Theory on FPGA
next chapter Half-Life Teaching Factor Based TLBO Algorithm
Literature
1.
Kariv, O., & Hakimi, S. L. (1969). An algorithmic approach to network location problems. II: The p-medians. SIAM Journal of Applied Mathematics, 37, 539–560.MathSciNetCrossRef
2.
Jayalakshmi, B., & Singh, A. (2018). Two swarm intelligence-based approaches for the p-centre problem. International Journal of Swarm Intelligence, 3(4), 290–308.CrossRef
3.
4.
Handler, G. Y. (1990). p-center problems. In Discrete location theory (pp. 305–315). Wiley.
5.
Daskin, M. S. (1995). Network and discrete location: Models, algorithms, and application. Wiley.
6.
Caruso, C., Colorni, A., & Aloi, L. (2003). Dominant, an algorithm for the p-center problem. European Journal of Operational Research, 149(1), 53–64.MathSciNetCrossRef
7.
Mladenovic, N., Labbe, M., & Hansen, P. (2003). Solving the p-center problem with tabu search and variable neighborhood search. Networks, 42(1), 48–64.MathSciNetCrossRef
8.
Pacheco, J. A., & Casado, S. (2005). Solving two location models with few facilities by using a hybrid heuristic: A real health resources case. Computers & Operations Research, 32(12), 3075–3091.CrossRef
9.
Chen, D., & Chen, R. (2009). New relaxation-based algorithms for the optimal solution of the continuous and discrete p-center problems. Computers & Operations Research, 36(5), 1646–1655.MathSciNetCrossRef
10.
Davidovic, T., Ramljak, D., Selmic, M., & Teodorovic, D. (2011). Bee colony optimization for the p-center problem. Computers & Operations Research, 38(10), 1367–1376.MathSciNetCrossRef
11.
Julstrom, B. A. (2009). Greedy heuristics for the bounded diameter minimum spanning tree problem. ACM Journal of Experimental Algorithmics, 14(1), 1–14.MathSciNetMATH
12.
Patvardhan, C., & Prakash, V. P. (2009, December). Novel deterministic heuristics for building minimum spanning trees with constrained diameter. Pattern Recognition and Machine Intelligence, LNCS 5909 (pp. 68–73).
13.
Patvardhan, C., Prakash, V. P., & Srivastav, A. (2014). Parallel heuristics for the bounded diameter minimum spanning tree problem. In India Conference (INDICON), 2014 Annual IEEE, 11–13 December 2014 (pp. 1–5). IEEE Press.
14.
Patvardhan, C., Prakash, V. P., & Srivastav, A. (2015). Fast heuristics for large instances of the euclidean bounded diameter minimum spanning tree problem. Informatica (Slovenia), 39(3), 281–292.MathSciNet
15.
Prakash, V. P., Patvardhan, C., & Srivastav, A. (2018). Effective heuristics for the bi-objective euclidean bounded diameter minimum spanning tree problem. In P. Bhattacharyya, H. Sastry, V. Marriboyina, & R. Sharma (Eds.), Smart and innovative trends in next generation computing technologies (NGCT 2017). Singapore.
16.
Floyd, R. W. (1962). Algorithm 97: Shortest path. Communications of the ACM, 5(6), 345.CrossRef
17.
Kruskal, J. B. (1956). On the shortest spanning subtree and the travelling salesman problem. In Proceedings of the American Mathematical Society (pp. 48–50).
18.
Beasley, J. E. (1990). OR-library: Distributing test problems by electronic mail. Journal of the Operational Research Society, 41(11), 1069–1072.CrossRef
Metadata
Title
A Comparison of the Effectiveness of Two Novel Clustering-Based Heuristics for the p-Centre Problem
Authors
Mahima Yadav
V. Prem Prakash
Copyright Year
2020
Publisher
Springer Singapore
Book
Advances in Data and Information Sciences

Print ISBN: 978-981-15-0693-2

Electronic ISBN: 978-981-15-0694-9

Copyright Year: 2020

DOI
https://doi.org/10.1007/978-981-15-0694-9_24