Minimax Regret Single-Facility Ordered Median Location Problems on Networks

References

• Ahuja R. K., Magnanti T. L., Orlin J. B.Network Flows (1993) (Prentice-Hall, Englewood Cliffs, NJ) Google Scholar
• Aissi H., Bazgan C., Vanderpooten D. Approximation of min-max and min-max regret versions of some combinatorial optimization problems. Eur. J. Oper. Res. (2007) 179:281–290Crossref, Google Scholar
• Averbakh I. On the complexity of a class of combinatorial optimization problems with uncertainty. Math. Programming (2001) 90:263–272Crossref, Google Scholar
• Averbakh I. Complexity of robust single facility location problems on networks with uncertain edge lengths. Discrete Appl. Math. (2003) 127:505–522Crossref, Google Scholar
• Averbakh I. The minimax relative regret median problem on networks. INFORMS J. Comput. (2005) 17:451–461Link, Google Scholar
• Averbakh I., Bereg S. Facility location problems with uncertainty on the plane. Discrete Optim. (2005) 2:3–34Crossref, Google Scholar
• Averbakh I., Berman O. Minimax regret p-center location on a network with demand uncertainty. Location Sci. (1997) 5:247–254Crossref, Google Scholar
• Averbakh I., Berman O. Algorithms for the robust 1-center problem on a tree. Eur. J. Oper. Res. (2000a) 123:292–302Crossref, Google Scholar
• Averbakh I., Berman O. Minmax regret median location on a network under uncertainty. INFORMS J. Comput. (2000b) 12:104–110Link, Google Scholar
• Averbakh I., Berman O. An improved algorithm for the minmax regret median problem on a tree. Networks (2003) 41:97–103Crossref, Google Scholar
• Averbakh I., Lebedev V. On the complexity of minmax regret linear programming. Eur. J. Oper. Res. (2005) 160:227–231Crossref, Google Scholar
• Brodal G. S., Georgiadis L., Katriel I. An O(n log n) version of the Averbakh-Berman algorithm for the robust median of a tree. Oper. Res. Lett. (2008) 36:14–16Crossref, Google Scholar
• Burkard R. E., Dollani H. Robust location problems with pos/neg weights on a tree. Networks (2001) 38:102–113Crossref, Google Scholar
• Burkard R. E., Dollani H. A note on the robust 1-center problem on trees. Ann. Oper. Res. (2002) 110:69–82Crossref, Google Scholar
• Carrizosa E., Conde E., Fernandez F. R., Puerto J. Multi-criteria analysis with partial information about the weighting coefficients. Eur. J. Oper. Res. (1995) 81:291–301Crossref, Google Scholar
• Chaudhuri S., Zaroliagis C. Shortest paths in digraphs of small treewidth. Part II: Optimal parallel algorithms. Theoret. Comput. Sci. (1998) 203:205–223Crossref, Google Scholar
• Chaudhuri S., Zaroliagis C. Shortest paths in digraphs of small treewidth. Part I: Sequential algorithms. Algorithmica (2000) 27:212–226Crossref, Google Scholar
• Chen B., Li C. S. Minmax-regret robust 1-median location on a tree. Networks (1998) 31:93–103Crossref, Google Scholar
• Cohen E. Efficient parallel shortest-paths in digraphs with a separator decomposition. J. Algorithms (1996) 21:331–357Crossref, Google Scholar
• Cole R. Slowing down sorting networks to obtain faster sorting algorithms. J. Assoc. Comput. Machinery (1987) 34:200–208Crossref, Google Scholar
• Conde E. An improved algorithm for selecting p items with uncertain returns according to the minmax-regret criterion. Math. Programming (2004) 100:345–353Crossref, Google Scholar
• Conde E. Minmax regret location-allocation problem on a network under uncertainty. Eur. J. Oper. Res. (2007) 179:1025–1039Crossref, Google Scholar
• Conde E. A note on the minmax regret centdian location on trees. Oper. Res. Lett. (2008) 36:271–275Crossref, Google Scholar
• Fernández F. R., Nickel S., Puerto J., Rodríguez-Chía A. M. Robustness in the Pareto-solutions for the multi-criteria minisum location problem. J. Multicriteria Decision Anal. (2001) 10:191–203Crossref, Google Scholar
• Henzinger M. R., Klein P., Rao S., Subramanian S. Faster shortest-path algorithms for planar graphs. J. Comput. System Sci. (1997) 55:3–23Crossref, Google Scholar
• Hershberger J., Suri S. Off-line maintenance of planar configurations. J. Algorithms (1996) 21:453–475Crossref, Google Scholar
• Kalcsics J., Nickel S., Puerto J., Tamir A. Algorithmic results for ordered median problems defined on networks and the plane. Oper. Res. Lett. (2002) 30:149–158Crossref, Google Scholar
• Kouvelis P., Yu G.Robust Discrete Optimization and Its Applications (1997) (Kluwer Academic Publishers, Amsterdam) Crossref, Google Scholar
• Megiddo N. Combinatorial optimization with rational objective functions. Math. Oper. Res. (1979) 4:414–424Link, Google Scholar
• Megiddo N. Applying parallel computation algorithms in the design of serial algorithms. J. Assoc. Comput. Machinery (1983a) 30:852–865Crossref, Google Scholar
• Megiddo N. Linear-time algorithms for linear programming in ℝ3 and related problems. SIAM J. Comput. (1983b) 12:759–776Crossref, Google Scholar
• Megiddo N., Tamir A., Zemel E., Chandrasekaran R. An O(n log 2n) algorithm for the k-th longest path in a tree with applications to location problems. SIAM J. Comput. (1981) 10:328–337Crossref, Google Scholar
• Nickel S., Puerto J. A unified approach to network location problems. Networks (1999) 34:283–290Crossref, Google Scholar
• Nickel S., Puerto J.Location Theory: A Unified Approach (2005) (Springer-Verlag, Heidelberg, Germany) Google Scholar
• Puerto J., Rodríguez-Chía A. M. Robust positioning of service units. Stochastic Models (2003) 19:125–147Crossref, Google Scholar
• Rodríguez-Chía A. M., Nickel S., Puerto J., Fernández F. R. A flexible approach to location problems. Math. Methods Oper. Res. (2000) 51:69–89Crossref, Google Scholar
• Tamir A. On the solution value of the continuous p-center location problem on a graph. Math. Oper. Res. (1987) 12:340–349Link, Google Scholar
• Tamir A. The k-centrum multi-facility location problem. Discrete Appl. Math. (2001) 109:292–307Crossref, Google Scholar
• Vairaktarakis G. L., Kouvelis P. Incorporation dynamic aspects and uncertainty in 1-median location problems. Naval Res. Logist. (1999) 46:147–168Crossref, Google Scholar
• Valiant L. G. Parallelism in comparison problems. SIAM J. Comput. (1975) 4:21–23Crossref, Google Scholar
• Yu H.-I., Lin T.-C., Wang B.-F. Improved algorithms for the minmax-regret 1-center and 1-median problems. ACM Trans. Algorithms (2008) 4(3):36Crossref, Google Scholar
• Zemel E. On search over rationals. Oper. Res. Lett. (1981) 1:34–38Crossref, Google Scholar
• Zemel E. An O(n) algorithm for the linear multiple choice knapsack problem and related problems. Inform. Processing Lett. (1984) 18:123–128Crossref, Google Scholar