IDEAS home Printed from https://ideas.repec.org/p/nwu/cmsems/379.html
   My bibliography  Save this paper

An O(n log2 n) Algorithm for the kth Longest Path in a Tree with Applications to Location Problems

Author

Listed:
  • N. Megiddo

Abstract

No abstract is available for this item.

Suggested Citation

  • N. Megiddo, 1979. "An O(n log2 n) Algorithm for the kth Longest Path in a Tree with Applications to Location Problems," Discussion Papers 379, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    • Handle: RePEc:nwu:cmsems:379
    as

    Download full text from publisher

    File URL: http://www.kellogg.northwestern.edu/research/math/papers/379.pdf
    File Function: main text
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Bennett Fox, 1966. "Discrete Optimization Via Marginal Analysis," Management Science, INFORMS, vol. 13(3), pages 210-216, November.
    2. Gabriel Y. Handler, 1978. "Finding Two-Centers of a Tree: The Continuous Case," Transportation Science, INFORMS, vol. 12(2), pages 93-106, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Haris Aziz & Hau Chan & Barton E. Lee & Bo Li & Toby Walsh, 2019. "Facility Location Problem with Capacity Constraints: Algorithmic and Mechanism Design Perspectives," Papers 1911.09813, arXiv.org.
    2. Arie Tamir & Eitan Zemel, 1979. "Locating Centers on a Tree with Discontinuous Supply and Demand Regions," Discussion Papers 397, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    3. Sven de Vries & Marc Posner & Rakesh Vohra, 2003. "Polyhedral Properties of the K -median Problem on a Tree," Discussion Papers 1367, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    4. J. Puerto & A. M. Rodríguez-Chía & A. Tamir, 2009. "Minimax Regret Single-Facility Ordered Median Location Problems on Networks," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 77-87, February.
    5. Sourour Elloumi & Martine Labbé & Yves Pochet, 2004. "A New Formulation and Resolution Method for the p-Center Problem," INFORMS Journal on Computing, INFORMS, vol. 16(1), pages 84-94, February.
    6. Eitan Zemel, 1980. "On Search Over Rationals," Discussion Papers 455, Northwestern University, Center for Mathematical Studies in Economics and Management Science.

    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.
    1. Ching, Wai Ki, 1997. "Markov-modulated Poisson processes for multi-location inventory problems," International Journal of Production Economics, Elsevier, vol. 53(2), pages 217-223, November.
    2. Mustafa Doğru & A. Kok & G. Houtum, 2013. "Newsvendor characterizations for one-warehouse multi-retailer inventory systems with discrete demand under the balance assumption," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 21(3), pages 541-559, September.
    3. Xiuli Chao & Liming Liu & Shaohui Zheng, 2003. "Resource Allocation in Multisite Service Systems with Intersite Customer Flows," Management Science, INFORMS, vol. 49(12), pages 1739-1752, December.
    4. Anh Ninh & Benjamin Melamed & Yao Zhao, 2020. "Analysis and optimization of recruitment stocking problems," Annals of Operations Research, Springer, vol. 295(2), pages 747-767, December.
    5. Kochel, P., 2007. "Order optimisation in multi-location models with hub-and-spoke structure," International Journal of Production Economics, Elsevier, vol. 108(1-2), pages 368-387, July.
    6. Thomas L. Morin & Roy E. Marsten, 1974. "Brand-and-Bound Strategies for Dynamic Programming," Discussion Papers 106, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    7. Xiaobo Zhao & Fan Fan & Xiaoliang Liu & Jinxing Xie, 2007. "Storage-Space Capacitated Inventory System with ( r, Q ) Policies," Operations Research, INFORMS, vol. 55(5), pages 854-865, October.
    8. Benjaafar, Saifallah, 1995. "Performance bounds for the effectiveness of pooling in multi-processing systems," European Journal of Operational Research, Elsevier, vol. 87(2), pages 375-388, December.
    9. Yossi Aviv & Awi Federgruen, 2001. "Design for Postponement: A Comprehensive Characterization of Its Benefits Under Unknown Demand Distributions," Operations Research, INFORMS, vol. 49(4), pages 578-598, August.
    10. Li Ding & Kevin D. Glazebrook & Christopher Kirkbride, 2008. "Allocation Models and Heuristics for the Outsourcing of Repairs for a Dynamic Warranty Population," Management Science, INFORMS, vol. 54(3), pages 594-607, March.
    11. Sridhar Seshadri & Jayashankar M. Swaminathan, 2003. "A componentwise index of service measurement in multi‐component systems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 50(2), pages 184-194, March.
    12. Feng Cheng* & Markus Ettl & Yingdong Lu & David D. Yao, 2012. "A Production–Inventory Model for a Push–Pull Manufacturing System with Capacity and Service Level Constraints," Production and Operations Management, Production and Operations Management Society, vol. 21(4), pages 668-681, July.
    13. Sumit Kunnumkal & Huseyin Topaloglu, 2008. "A duality‐based relaxation and decomposition approach for inventory distribution systems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(7), pages 612-631, October.
    14. Özalp Özer, 2003. "Replenishment Strategies for Distribution Systems Under Advance Demand Information," Management Science, INFORMS, vol. 49(3), pages 255-272, March.
    15. Richard L. Francis, 2009. "Location Theory Helps Solve a Double-Vision Problem," Interfaces, INFORMS, vol. 39(6), pages 527-532, December.
    16. Frenk, J.B.G. & Labbé, M. & van Vliet, M. & Zhang, S., 1994. "Improved algorithms for machine allocation in manufacturing systems," Econometric Institute Research Papers 11742, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    17. Driessen, M.A. & van Houtum, G.J. & Zijm, W.H.M. & Rustenburg, W.D., 2020. "Capacity assignment in repair shops with high material uncertainty," International Journal of Production Economics, Elsevier, vol. 221(C).
    18. Christiane B. Haubitz & Ulrich W. Thonemann, 2021. "How to Change a Running System—Controlling the Transition to Optimized Spare Parts Inventory Policies," Production and Operations Management, Production and Operations Management Society, vol. 30(5), pages 1386-1405, May.
    19. Xiao Yu & Armagan Bayram, 2021. "Managing capacity for virtual and office appointments in chronic care," Health Care Management Science, Springer, vol. 24(4), pages 742-767, December.
    20. Gergely Mincsovics & Nico Dellaert, 2010. "Stochastic dynamic nursing service budgeting," Annals of Operations Research, Springer, vol. 178(1), pages 5-21, July.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    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:nwu:cmsems:379. 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: Fran Walker (email available below). General contact details of provider: https://edirc.repec.org/data/cmnwuus.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.