zbMATH — the first resource for mathematics

Deterministic algorithm for 1-median 1-center two-objective optimization problem. (English) Zbl 1460.90172
Hajiaghayi, Mohammad Taghi (ed.) et al., Topics in theoretical computer science. The first IFIP WG 1.8 international conference, TTCS 2015, Tehran, Iran, August 26–28, 2015. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 9541, 164-178 (2016).
Summary: $$k$$-median and $$k$$-center are two well-known problems in facility location which play an important role in operation research, management science, clustering and computational geometry. To the best of our knowledge, although these problems have lots of applications, they have never been studied together simultaneously as a multi objective optimization problem. Multi-objective optimization has been applied in many fields of science where optimal decisions need to be taken in the presence of trade-offs between two or more conflicting objectives. In this paper we consider 1-median and 1-center two-objective optimization problem. We prove that $$\varOmega (n\log {n})$$ is a lower bound for proposed problem in one and two dimensions in Manhattan metric. Also, by using the properties of farthest point Voronoi diagram, we present a deterministic algorithm which output the Pareto Front and Pareto Optimal Solutions in $$\mathcal {O}(n\log {n})$$ time.
For the entire collection see [Zbl 1329.68028].

MSC:
 90C29 Multi-objective and goal programming 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
Full Text: