Top

Journal of Combinatorial Optimization

Published in:

01-03-2023

The balanced 2-median and 2-maxian problems on a tree

Authors: Jafar Fathali, Mehdi Zaferanieh

Published in: Journal of Combinatorial Optimization | Issue 2/2023

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

search-config

AI-assisted search

Off

Abstract

This paper deals with the facility location problems on a balancing allocation approach. Two location models are proposed, which are convex combinations of the traditional p-median and p-maxian problems together with minimizing the maximum demand level allocated to any facility. An edge deletion method with time complexity \(O(n^2)\) is represented for the balanced 2-median problem on a tree. For the balanced 2-maxian problem, it is shown the optimal solution is two end vertices of the longest path of the tree, which can be obtained in linear time.

previous article The two-center problem of uncertain points on a real line

next article An equilibrium analysis of the impact of real estate price volatility on macroeconomics based on ant colony algorithm

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 "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

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

Berman O, Drezner Z, Tamir A, Wesolowsky GO (2009) Optimal location with equitable loads. Ann Oper Res 167:307–325MathSciNetCrossRefMATH

Burkard RE, Fathali J, Kakhki HT (2007) The p-maxian problem on a tree. Oper Res Lett 35:331–335MathSciNetCrossRefMATH

Burkard RE, Çela E, Dollani H (2000) 2-Median in trees with pos/neg weights. Discret Appl Math 105:51–71MathSciNetCrossRefMATH

Daskin MS, Tucker EL (2018) The trade-off between the median and range of assigned demand in facility location models. Int J Prod Res 56:97–119. https://doi.org/10.1080/00207543.2017.1401751CrossRef

Eiselt HA, Laporte G (1995) Objectives in location problems. In: Facility location: a survey of applications and methods. Ed.: Drezner Z. Springer, Berlin, 151-180

Gavish B, Sridhar S (1995) Computing the 2-median on tree networks is \(O(n\log n)\) time. Networks 26:305–317MathSciNetCrossRefMATH

Hakimi SL (1964) Optimum locations of switching centers and the absolute centers and medians of a graph. Oper Res 12:450–459CrossRefMATH

Hakimi SL (1965) Optimum distribution of switching centers in a communication network and some related graph theoretic problems. Oper Res 13:462–475MathSciNetCrossRefMATH

Handler GY (1973) Minimax location of a facility in an undirected tree networks. Transp Sci 7:287–293CrossRef

Hansen P, Moon ID (1988) Dispersing facilities on a network. Presentation at the TIMS/ORSA Joint National Meeting, WashingtonMATH

Kariv O, Hakimi SL (1979) An algorithmic approach to network location problems Part II: p-medians. SIAM J Appl Math 37:539–560MathSciNetCrossRefMATH

Marin A (2011) The discrete facility location problem with balanced allocation of customers. Eur J Oper Res 210:27–38MathSciNetCrossRefMATH

Marsh MT, Schilling DA (1994) Equity measurement in facility location analysis—a review and framework. Eur J Oper Res 74:1–17CrossRefMATH

Nguyen TK, Hung NT, Nguyen-Thu H (2020) A linear time algorithm for the p-maxian problem on trees with distance constraint. J Comb Optim 40:1030–1043. https://doi.org/10.1007/s10878-020-00650-9MathSciNetCrossRefMATH

Oudjit A, Stallmann MF (2021) Efficient algorithms for finding 2-medians of a tree. Networks 77:383–402. https://doi.org/10.1002/net.21978MathSciNetCrossRef

Schulz C, Strash D (2018) Graph partitioning: formulations and applications to big data. In: Sakr S, Zomaya A (eds). Encyclopedia of Big Data Technologies. Springer, Cham https://doi.org/10.1007/978-3-319-63962-8_312-2

Tamir A (1996) An \(O(pn^2)\) algorithm for the p-median and related problems on tree graphs. Oper Res Lett 19:59–64MathSciNetCrossRefMATH

Title: The balanced 2-median and 2-maxian problems on a tree
Authors: Jafar Fathali
Mehdi Zaferanieh
Publication date: 01-03-2023
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 2/2023
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-023-00997-9

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 2/2023

Matching random colored points with rectangles

Construction of minimum edge-fault tolerant connected dominating set in a general graph

On streaming algorithms for maximizing a supermodular function plus a MDR-submodular function on the integer lattice

Analysis of modern circulation industry development level using industrial structure mechanism

Analyzing the spatial association of household consumption carbon emission structure based on social network

Algorithm research on the influence of financing structure and cash holding on enterprise innovation based on system GMM model function theory

Premium Partner