Skip to main content
SpringerLink
Log in

A Linear Time Algorithm for Computing Minmax Regret 1-Median on a Tree Network

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

In a model of facility location problem, the uncertainty in the weight of a vertex is represented by an interval of weights, and the objective is to minimize the maximum “regret.” The most efficient algorithm previously known for finding the minmax regret 1-median in a tree network with nonnegative vertex weights takes O(nlogn) time. We improve it to O(n), settling the open problem posed by Brodal et al. (Oper. Res. Lett. 36:14–18, 2008).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Notes

  1. We use the term ‘node’ to avoid confusion with a vertex of T.

  2. If |S min(r)| is odd, one scenario is left unpaired.

  3. In the first round, where r=r 0, for example, this scenario may be s c(v a ) or s c(v b ). In general such a scenario belongs to S min(r) and its front is r. It is easy to compute its median.

  4. We use the term ‘node’ here to distinguish it from a vertex of tree T.

  5. Note that all leaves of τ D are at level ⌊logt⌋ or higher (closer to the root).

  6. If these two paths intersect, then some medians needed for OptBranch(S,y k ) may have already been computed, and they need not be recomputed.

References

  1. Averbakh, I., Berman, O.: Minmax regret median location on a network under uncertainty. INFORMS J. Comput. 12(2), 104–110 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  2. Averbakh, I., Berman, O.: An improved algorithm for the minmax regret median problem on a tree. Networks 41, 97–103 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  3. Bhattacharya, B., Kameda, T.: Linear time algorithm for finding minmax regret 1-median on a tree with positive vertex weights. In: Proc. 18th Annual International Computing and Combinatorics Conference (COCOON). LNCS, vol. 7434, pp. 1–12. Springer, Berlin (2012)

    Google Scholar 

  4. Bhattacharya, B., Kameda, T., Song, Z.: Computing minmax regret 1-median on a tree network with positive/negative vertex weights. In: Proc. 23rd Int’l Symp. on Algorithms and Computation (ISAAC). LNCS, vol. 7676, pp. 588–597. Springer, Berlin (2012)

    Google Scholar 

  5. Brodal, G.S., Georgiadis, L., Katriel, I.: An O(nlogn) version of the Averbakh–Berman algorithm for the robust median of a tree. Oper. Res. Lett. 36, 14–18 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  6. Burkard, R.E., Dollani, H.: Robust location problems with pos/neg weights on a tree. Networks 38(2), 102–113 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  7. Chan, C.Y., Ku, S.C., Lu, C.J., Wang, B.F.: Efficient algorithms for two generalized 2-median problems and the group median problem on trees. Theor. Comput. Sci. 410, 867–876 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  8. Chen, B., Lin, C.S.: Minmax-regret robust 1-median location on a tree. Networks 31, 93–103 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  9. Goldman, A.: Optimal center location in simple networks. Transp. Sci. 5, 212–221 (1971)

    Article  Google Scholar 

  10. Hale, T.S., Moberg, C.R.: Location science research: a review. Ann. Oper. Res. 123, 21–35 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  11. Kariv, O., Hakimi, S.: An algorithmic approach to network location problems, part 2: The p-median. SIAM J. Appl. Math. 37, 539–560 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  12. Kouvelis, P., Vairaktarakis, G., Yu, G.: Robust 1-median location on a tree in the presence of demand and transportation cost uncertainty. Tech. Rep. Working paper 93/94-3-4, Department of Management Science, The University of Texas, Austin (1993)

  13. Kouvelis, P., Yu, G.: Robust Discrete Optimization and Its Applications. Kluwer Academic, London (1997)

    Book  MATH  Google Scholar 

  14. Megiddo, N.: Linear-time algorithms for linear-programming in R 3 and related problems. SIAM J. Comput. 12, 759–776 (1983)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  16. Yu, H.I., Lin, T.C., Wang, B.F.: Improved algorithms for the minmax-regret 1-center and 1-median problem. ACM Trans. Algorithms 4(3), 1 (2008)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

We greatly appreciate the comments provided by the anonymous referees, who pointed out some deficiencies in the original manuscript, and who patiently perused the two revisions of this relatively long paper. This work was supported in part by Discovery Grants of the Natural Sciences and Engineering Research Council of Canada, held by B. Bhattacharya and T. Kameda, and a MITACS grant held by B. Bhattacharya.

Author information

Authors and Affiliations

  1. School of Computing Science, Simon Fraser University, Burnaby, Canada

    Binay Bhattacharya & Tsunehiko Kameda

  2. Department of Computer Science, The University of Texas at Austin, Austin, TX, USA

    Zhao Song

Authors
  1. Binay Bhattacharya
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tsunehiko Kameda
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Zhao Song
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tsunehiko Kameda.

Additional information

Zhao Song took part in this work while he was an undergraduate student at SFU.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bhattacharya, B., Kameda, T. & Song, Z. A Linear Time Algorithm for Computing Minmax Regret 1-Median on a Tree Network. Algorithmica 70, 2–21 (2014). https://doi.org/10.1007/s00453-013-9851-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-013-9851-7

Keywords

Search

Navigation