A quadratic time exact algorithm for continuous connected 2-facility location problem in trees
Author
Abstract
Suggested Citation
DOI: 10.1007/s10878-017-0213-2
Download full text from publisher
As the access to this document is restricted, you may want to search for a different version of it.
References listed on IDEAS
- S. S. Ting, 1984. "A Linear-Time Algorithm for Maxisum Facility Location on Tree Networks," Transportation Science, INFORMS, vol. 18(1), pages 76-84, February.
- Schröer, Sebastian & Straubhaar, Thomas, 2007. "Demographische Entwicklung: Problem oder Phantom?," HWWI Policy Papers 1-1, Hamburg Institute of International Economics (HWWI).
- Rainer Burkard & Jafar Fathali, 2007. "A polynomial method for the pos/neg weighted 3-median problem on a tree," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 65(2), pages 229-238, April.
- Becker, Ronald I. & Lari, Isabella & Scozzari, Andrea, 2007. "Algorithms for central-median paths with bounded length on trees," European Journal of Operational Research, Elsevier, vol. 179(3), pages 1208-1220, June.
- Youngho Lee & Steve Y. Chiu & Jennifer Ryan, 1996. "A Branch and Cut Algorithm for a Steiner Tree-Star Problem," INFORMS Journal on Computing, INFORMS, vol. 8(3), pages 194-201, August.
- Jui-Chung Allen Li, 2007. "The Kids Are OK Divorce and Children's Behavior Problems," Working Papers WR-489, RAND Corporation.
- Wei Ding & Yu Zhou & Guangting Chen & Hongfa Wang & Guangming Wang, 2013. "On the 2-MRS Problem in a Tree with Unreliable Edges," Journal of Applied Mathematics, Hindawi, vol. 2013, pages 1-11, November.
- Richard L. Church & Robert S. Garfinkel, 1978. "Locating an Obnoxious Facility on a Network," Transportation Science, INFORMS, vol. 12(2), pages 107-118, May.
- Igor Averbakh & Oded Berman, 2000. "Minmax Regret Median Location on a Network Under Uncertainty," INFORMS Journal on Computing, INFORMS, vol. 12(2), pages 104-110, May.
- ., 2007. "Problems of Utility Privatization," Chapters, in: Paul Cook & Sarah Mosedale (ed.), Regulation, Markets and Poverty, chapter 8, Edward Elgar Publishing.
- George L. Vairaktarakis & Panagiotis Kouvelis, 1999. "Incorporation dynamic aspects and uncertainty in 1‐median location problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 46(2), pages 147-168, March.
- ., 2007. "Anti-dumping action - problems arising," Chapters, in: Anti-Dumping and Countervailing Action, chapter 5, Edward Elgar Publishing.
- Averbakh, Igor & Berman, Oded, 2000. "Algorithms for the robust 1-center problem on a tree," European Journal of Operational Research, Elsevier, vol. 123(2), pages 292-302, June.
- Rainer Burkard & Helidon Dollani, 2002. "A Note on the Robust 1-Center Problem on Trees," Annals of Operations Research, Springer, vol. 110(1), pages 69-82, February.
- ., 2007. "Subsidies and countervailing action - problems arising," Chapters, in: Anti-Dumping and Countervailing Action, chapter 7, Edward Elgar Publishing.
- Arie Tamir & Eitan Zemel, 1982. "Locating Centers on a Tree with Discontinuous Supply and Demand Regions," Mathematics of Operations Research, INFORMS, vol. 7(2), pages 183-197, May.
- Mohammad Khairul Hasan & Hyunwoo Jung & Kyung-Yong Chwa, 2008. "Approximation algorithms for connected facility location problems," Journal of Combinatorial Optimization, Springer, vol. 16(2), pages 155-172, August.
- Jui-Chung Allen Li, 2007. "The Kids Are OK Divorce and Children's Behavior Problems," Working Papers 489, RAND Corporation.
- Yu Zhou & Wei Ding & Guangming Wang & Guangting Chen, 2015. "An Edge-Turbulence Algorithm for the 2-MRS Problem on Trees with Unreliable Edges," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 32(01), pages 1-17.
- R. Ravi & Amitabh Sinha, 2006. "Approximation Algorithms for Problems Combining Facility Location and Network Design," Operations Research, INFORMS, vol. 54(1), pages 73-81, February.
- Burkard, R. E. & Dollani, Helidon, 2003. "Center problems with pos/neg weights on trees," European Journal of Operational Research, Elsevier, vol. 145(3), pages 483-495, March.
- Dickson, D. C. M., 2007. "Some Finite Time Ruin Problems," Annals of Actuarial Science, Cambridge University Press, vol. 2(2), pages 217-232, September.
- ., 2007. "A Statement of the Problem," Chapters, in: The Causes, Costs and Compensations of Inflation, chapter 1, Edward Elgar Publishing.
- A. J. Goldman, 1971. "Optimal Center Location in Simple Networks," Transportation Science, INFORMS, vol. 5(2), pages 212-221, May.
- G. Y. Handler, 1973. "Minimax Location of a Facility in an Undirected Tree Graph," Transportation Science, INFORMS, vol. 7(3), pages 287-293, August.
- M. Gisela Bardossy & S. Raghavan, 2010. "Dual-Based Local Search for the Connected Facility Location and Related Problems," INFORMS Journal on Computing, INFORMS, vol. 22(4), pages 584-602, November.
Most related items
These are the items that most often cite the same works as this one and are cited by the same works as this one.- Trung Kien Nguyen & Nguyen Thanh Hung & Huong Nguyen-Thu, 2020. "A linear time algorithm for the p-maxian problem on trees with distance constraint," Journal of Combinatorial Optimization, Springer, vol. 40(4), pages 1030-1043, November.
- Esmaeil Afrashteh & Behrooz Alizadeh & Fahimeh Baroughi, 2020. "Optimal approaches for upgrading selective obnoxious p-median location problems on tree networks," Annals of Operations Research, Springer, vol. 289(2), pages 153-172, June.
- Mehdi Zaferanieh & Jafar Fathali, 2012. "Finding a core of a tree with pos/neg weight," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 76(2), pages 147-160, October.
- Rainer E. Burkard & Johannes Hatzl, 2010. "Median problems with positive and negative weights on cycles and cacti," Journal of Combinatorial Optimization, Springer, vol. 20(1), pages 27-46, July.
- Rainer Burkard & Jafar Fathali, 2007. "A polynomial method for the pos/neg weighted 3-median problem on a tree," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 65(2), pages 229-238, April.
- Vatsa, Amit Kumar & Jayaswal, Sachin, 2021. "Capacitated multi-period maximal covering location problem with server uncertainty," European Journal of Operational Research, Elsevier, vol. 289(3), pages 1107-1126.
- Conde, Eduardo, 2007. "Minmax regret location-allocation problem on a network under uncertainty," European Journal of Operational Research, Elsevier, vol. 179(3), pages 1025-1039, June.
- Liying Kang & Yukun Cheng, 2010. "The p-maxian problem on block graphs," Journal of Combinatorial Optimization, Springer, vol. 20(2), pages 131-141, August.
- Balakrishnan, K. & Changat, M. & Mulder, H.M. & Subhamathi, A.R., 2011. "Consensus Strategies for Signed Profiles on Graphs," Econometric Institute Research Papers EI2011-34, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
- Chunsong Bai & Jun Du, 2024. "The Constrained 2-Maxian Problem on Cycles," Mathematics, MDPI, vol. 12(6), pages 1-9, March.
- Vatsa, Amit Kumar & Jayaswal, Sachin, 2015. "A New Formulation and Benders' Decomposition for Multi-period facility Location Problem with Server Uncertainty," IIMA Working Papers WP2015-02-07, Indian Institute of Management Ahmedabad, Research and Publication Department.
- Mulder, H.M. & Pelsmajer, M.J. & Reid, K.B., 2006. "Generalized centrality in trees," Econometric Institute Research Papers EI 2006-16, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
- Wang, Haitao, 2014. "Minmax regret 1-facility location on uncertain path networks," European Journal of Operational Research, Elsevier, vol. 239(3), pages 636-643.
- Vatsa, Amit Kumar & Jayaswal, Sachin, 2016. "A new formulation and Benders decomposition for the multi-period maximal covering facility location problem with server uncertainty," European Journal of Operational Research, Elsevier, vol. 251(2), pages 404-418.
- Igor Averbakh & Oded Berman, 2000. "Minmax Regret Median Location on a Network Under Uncertainty," INFORMS Journal on Computing, INFORMS, vol. 12(2), pages 104-110, May.
- Welch, S. B. & Salhi, S., 1997. "The obnoxious p facility network location problem with facility interaction," European Journal of Operational Research, Elsevier, vol. 102(2), pages 302-319, October.
- Contreras, Ivan & Fernández, Elena, 2012. "General network design: A unified view of combined location and network design problems," European Journal of Operational Research, Elsevier, vol. 219(3), pages 680-697.
- Van Huy Pham & Nguyen Chi Tam, 2019. "A combinatorial algorithm for the ordered 1-median problem on cactus graphs," OPSEARCH, Springer;Operational Research Society of India, vol. 56(3), pages 780-789, September.
- Berman, Oded & Wang, Jiamin, 2011. "The minmax regret gradual covering location problem on a network with incomplete information of demand weights," European Journal of Operational Research, Elsevier, vol. 208(3), pages 233-238, February.
- Batta, Rajan & Lejeune, Miguel & Prasad, Srinivas, 2014. "Public facility location using dispersion, population, and equity criteria," European Journal of Operational Research, Elsevier, vol. 234(3), pages 819-829.
More about this item
Keywords
Continuous connected 2-facility; Tree; Edge-splitting; Quadratic time;All these keywords.
Statistics
Access and download statisticsCorrections
All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:36:y:2018:i:4:d:10.1007_s10878-017-0213-2. See general information about how to correct material in RePEc.
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .
Please note that corrections may take a couple of weeks to filter through the various RePEc services.