Abstract
The network version of them-median problem with mutual communication (MMMC) is to find the location ofm new facilities on a network withn nodes such that the sum of (a) the cost of interaction between the new facilities andn existing facilities on the network, and (b) the cost of interaction between pairs of new facilities is minimized. The existing facilities are located at nodes of the network and the interaction cost between a pair of facilities is a function of the network distance between the facilities. This problem is shown to be equivalent to a graph-theoretic Node Selection Problem (NSP). We show that many other problems can be formulated as an NSP. We then provide a polynomial time algorithm to solve NSP for the case when the flow graph is Halin. Extensions to other graph families are provided.
Similar content being viewed by others
References
R.G. Askin and J.B. Goldberg, Economic optimization in product design, Eng. Opt. 14(1988)139–152.
F. Barahona, A solvable case of quadratic 0–1 programming, Discr. Appl. Math. 13(1986)23–26.
R.E. Bixby and D.K. Wagner, An almost linear-time algorithm for graph realization, Math. Oper. Res. 13(1988)99–123.
D. Chhajed and T.J. Lowe, Solving structured multifacility location problems efficiently, Transp. Sci. (1993), to appear.
D. Chhajed and T.J. Lowe,M-median andM-center problems with mutual communication: Solvable special cases, Oper. Res. 40(1992)S56-S66.
D.G. Corneil and J.M. Keil, A dynamic programming approach to the dominating set problem onK-trees, SIAM J. Alg. Discr. Meth. 8(1987)535–543.
P.M. Dearing, R.L. Francis and T.J. Lowe, Convex location problems on tree networks, Oper. Res. 24(1976)628–642.
S.E. Eriksen and P.D. Berger, A quadratic programming model for product configuration optimization, Zeits. Oper. Res. 31(1987)B143-B159.
E. Erkut, R.L. Francis and T.J. Lowe, A multimedian problem with interdistance constraints, Environ. Planning B: Planning and Design 15(1988)181–190
E. Erkut, R.L. Francis, T.J. Lowe and A. Tamir, Equivalent mathematical programming formulations of monotonic tree network location problems, Oper. Res. 37(1989)447–461.
R.L. Francis, T.J. Lowe and H.D. Ratliff, Distance constraints for tree network multifacility location problems, Oper. Res. 26(1978)570–596.
J.E. Hopcroft and R.E. Tarjan, Dividing a graph into triconnected components, SIAM J. Comput. 2(1973)135–158.
A. Kolen, Location problems on trees and in the rectilinear plane, Stichting Mathematisch Centrum, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands (1982).
R.L. Lipton and R.E. Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math. 36(1979)177–189.
R.J. Lipton and R.E. Tarjan, Applications of a planar separator theorem, SIAM J. Comput. 9(1980)615–627.
P.M. Pardalos and S. Jha, Graph separation techniques for quadratic zero-one programming (1990), Computer Science Department, The Pennsylvania State University, to appear in Comput. Math. Appl.
J.-C. Picard and H.D. Ratliff, A cut approach to the rectilinear distance facility location problem, Oper. Res. 28(1978)422–433.
T.V. Wimer, Linear algorithms onk-terminal graphs, Report No. URI-030, Clemson University (1987).
Y. Xu, R.L. Francis and T.J. Lowe, The multimedian problem on a network: Exploiting block structure, Working Paper, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL (1988).
W. Domschke, Schedule synchronization for public transit networks, OR Spektrum 11(1989)17–24.
M.B. Richey, Optimal location of a path or tree on a network with cycles, Working Paper, George Mason University, Fairfax, VA (1989).
G. Cornuejols, D. Naddef and W. Pulleyblank, The traveling salesman problem in graphs with 3-edge cutsets, J. ACM 32(1985)383–410.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Chhajed, D., Lowe, T.J. Locating facilities which interact: Some solvable cases. Ann Oper Res 40, 101–124 (1992). https://doi.org/10.1007/BF02060472
Issue Date:
DOI: https://doi.org/10.1007/BF02060472