×

Lexicographic local search and the \(p\)-center problem. (English) Zbl 1053.90052

Summary: We introduce a local search strategy that suits combinatorial optimization problems with a min-max (or max-min) objective. According to this approach, solutions are compared lexicographically rather then by their worst coordinate. We apply this approach to the \(p\)-center problem.

MSC:

90B40 Search theory
90C59 Approximation methods and heuristics in mathematical programming

Software:

TSPLIB
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cooper, L., Location-allocation problems, Operations Research, 11, 331-343 (1963) · Zbl 0113.14201
[2] Drezner, Z., The \(p\)-center problem-heuristics and optimal algorithms, Journal of the Operational Research Society, 35, 741-748 (1984) · Zbl 0544.90024
[3] Dyer, M. E.; Frieze, A. M., A simple heuristic for the \(p\)-center problem, Operations Research Letters, 3, 285-288 (1985) · Zbl 0556.90019
[4] Fowler, R. J.; Paterson, M. S.; Tanimoto, S. L., Optimal packing and covering in the plane are NP-complete, Information Processing Letters, 12, 133-137 (1987) · Zbl 0469.68053
[5] M. Fürer, B. Raghavachari, Approximating the minimum degree spanning tree to within one from the optimal degree, in: Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, 1992; M. Fürer, B. Raghavachari, Approximating the minimum degree spanning tree to within one from the optimal degree, in: Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, 1992 · Zbl 0829.68097
[6] Fürer, M.; Raghavachari, B., Approximating the minimum degree Steiner tree to within one of optimal, Journal of Algorithms, 17, 409-423 (1994) · Zbl 1321.05262
[7] Glass, C. A.; Potts, C. N.; Shade, P., Unrelated parallel machine scheduling using local search, Mathematical and Computer Modeling, 20, 41-52 (1994) · Zbl 0810.90066
[8] Grötschel, M.; Holland, O., Solution of large-scale symmetric travelling salesman problems, Mathematical Programming, 51, 141-202 (1991) · Zbl 0733.90047
[9] Handler, G. Y.; Mirchandani, P., Location on Networks, Theory and Algorithms (1979), M.I.T. Press: M.I.T. Press Cambridge, MA · Zbl 0533.90026
[10] Hochbaum, D. S.; Shmoys, D. B., A best possible heuristic for the \(k\)-center problem, Mathematics of Operations Research, 10, 180-184 (1985) · Zbl 0565.90015
[11] Hochbaum, D. S.; Shmoys, D. B., A unified approach to approximation algorithms for bottleneck problems, Journal of the Association for Computing Machinery, 33, 533-550 (1986)
[12] S. Khanna, R. Motwani, M. Sudan, U. Vazirani, On syntactic versus computational views of approximability, in: Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 819-830; S. Khanna, R. Motwani, M. Sudan, U. Vazirani, On syntactic versus computational views of approximability, in: Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 819-830 · Zbl 0915.68068
[13] Plesnı́k, J., A heuristic for the \(p\)-center problem in graphs, Discrete Applied Mathematics, 17, 263-268 (1987) · Zbl 0637.05020
[14] Plesnı́k, J., On the interchange heuristic for locating centers and medians in a graph, Mathematica Slovaca, 37, 209-216 (1987) · Zbl 0642.05030
[15] G. Reinelt, TSPLIB. Available from <ftp://elib.zib-berlin.de/pub/mp-testdata/tsp/index.html; G. Reinelt, TSPLIB. Available from <ftp://elib.zib-berlin.de/pub/mp-testdata/tsp/index.html
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.