×

The inverse 1-maxian problem with edge length modification. (English) Zbl 1180.90165

Summary: We consider the problem of modifying the lengths of the edges of a graph at minimum cost such that a prespecified vertex becomes a 1-maxian with respect to the new edge lengths. The inverse 1-maxian problem with edge length modification is shown to be strongly \(\mathcal{N}\mathcal{P}\)-hard and remains weakly \(\mathcal{NP}\)-hard even on series-parallel graphs. Moreover, a transformation of the inverse 1-maxian problem with edge length modification on a tree to a minimum cost circulation problem is given which solves the original problem in \(\mathcal{O}(n\log n)\).

MSC:

90B80 Discrete location and assignment
90C60 Abstract computational complexity for mathematical programming problems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows: theory, algorithms, and applications. Prentice Hall, New Jersey
[2] Bein WW, Brucker P, Tamir A (1985) Minimum cost flow algorithms for series-parallel networks. Discret Appl Math 10:117–124 · Zbl 0571.90019 · doi:10.1016/0166-218X(85)90006-X
[3] Berman O, Ingco DI, Odoni A (1992) Improving the location of minisum facilities through network modification. Ann Oper Res 40:1–16 · Zbl 0787.90035 · doi:10.1007/BF02060467
[4] Berman O, Ingco DI, Odoni A (1994) Improving the location of minimax facilities through network modification. Networks 24:31–41 · Zbl 0799.90074 · doi:10.1002/net.3230240105
[5] Booth H, Tarjan RE (1993) Finding the minimum-cost maximum flow in a series-parallel network. J Algorithms 15:416–446 · Zbl 0795.90018 · doi:10.1006/jagm.1993.1048
[6] Burkard RE, Pleschiutschnig C, Zhang J (2004) Inverse median problems. Discret Optim 1:23–39 · Zbl 1087.90038 · doi:10.1016/j.disopt.2004.03.003
[7] Burkard RE, Gassner E, Hatzl J (2006) A linear time algorithm for the reverse 1-median problem on a cycle. Networks 48:16–23 · Zbl 1103.90082 · doi:10.1002/net.20115
[8] Burkard RE, Gassner E, Hatzl J (2007) Reverse 2-median problem on trees, accpeted for publication in Discret Appl Math · Zbl 1216.90072
[9] Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, New York · Zbl 0411.68039
[10] Goldman AJ (1971) Optimum center location in simple networks. Transp Sci 5:212–221 · doi:10.1287/trsc.5.2.212
[11] Henzinger MR, Klein PN, Rao S, Subramanian S (1997) Faster shortest-path algorithms for planar graphs. J Comput Syst Sci 55:3–23 · Zbl 0880.68099 · doi:10.1006/jcss.1997.1493
[12] Heuberger C (2004) Inverse combinatorial optimization: a survey on problems, methods, and results. J Comb Optim 8:329–361 · Zbl 1084.90035 · doi:10.1023/B:JOCO.0000038914.26975.9b
[13] Robertson N, Seymour PD (1986) Graph minors II. Algorithmic aspects of tree-width. J Algorithms 7:309–322 · Zbl 0611.05017 · doi:10.1016/0196-6774(86)90023-4
[14] Tamir A (1991) Obnoxious facility location on graphs. SIAM J Discret Math 4:550–567 · Zbl 0737.05063 · doi:10.1137/0404048
[15] Ting SS (1984) A linear-time algorithm for maxisum facility location on tree networks. Transp Sci 18:76–84 · doi:10.1287/trsc.18.1.76
[16] Zhang JZ, Yang XG, Cai MC (1999) Reverse center location problem. Lect Notes Comput Sci 1741:279–294 · Zbl 0968.90048 · doi:10.1007/3-540-46632-0_29
[17] Zhang J, Liu Z, Ma Z (2000) Some reverse location problems. Eur J Oper Res 124:77–88 · Zbl 0960.90056 · doi:10.1016/S0377-2217(99)00122-8
[18] Zhang JZ, Yang XG, Cai MC (2004) Inapproximability and a polynomially solvable special case of a network improvement problem. Eur J Oper Res 155:251–257 · Zbl 1045.90011 · doi:10.1016/S0377-2217(02)00876-7
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.