In this chapter, we first give a brief introduction to the inverse center and median location problems under different norms. Then we mainly consider the inverse vertex obnoxious 1-center location problem (IVO1C) on a general graph G. We aim to adjust the edge weights satisfying upper and lower bounds with the least cost, so that a given vertex s becomes the obnoxious 1-center of graph G. We construct their mathematical models and prove some properties under the weighted \(l_\infty \) norm and bottleneck Hamming distance. We design an \(O(n^3)\) time algorithm to solve the problem (IVO1C \(_\infty \) ) by solving the transcendence point of the cost function in each iteration, where n is the number of vertices in the graph G. We also propose a binary search method for the problem (IVO1C \(_{bH}\) ) with time complexity \(O(n^2\log n)\) . Finally, we show some computational experiments to verify the effectiveness of the algorithms.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Inverse Vertex Obnoxious 1-Center Location Problems

  • Xiucui Guan,
  • Panos M. Pardalos,
  • Binwu Zhang

摘要

In this chapter, we first give a brief introduction to the inverse center and median location problems under different norms. Then we mainly consider the inverse vertex obnoxious 1-center location problem (IVO1C) on a general graph G. We aim to adjust the edge weights satisfying upper and lower bounds with the least cost, so that a given vertex s becomes the obnoxious 1-center of graph G. We construct their mathematical models and prove some properties under the weighted \(l_\infty \) norm and bottleneck Hamming distance. We design an \(O(n^3)\) time algorithm to solve the problem (IVO1C \(_\infty \) ) by solving the transcendence point of the cost function in each iteration, where n is the number of vertices in the graph G. We also propose a binary search method for the problem (IVO1C \(_{bH}\) ) with time complexity \(O(n^2\log n)\) . Finally, we show some computational experiments to verify the effectiveness of the algorithms.