Deterministic Algorithm for 1-Median 1-Center Two-Objective Optimization Problem

Abstract : 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})$.
Type de document :
Communication dans un congrès
Mohammed Taghi Hajiaghayi; Mohammad Reza Mousavi. 1st International Conference on Theoretical Computer Science (TTCS), Aug 2015, Tehran, Iran. Lecture Notes in Computer Science, LNCS-9541, pp.164-178, 2016, Topics in Theoretical Computer Science. 〈10.1007/978-3-319-28678-5_12〉
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01446259
Contributeur : Hal Ifip <>
Soumis le : mercredi 25 janvier 2017 - 16:50:45
Dernière modification le : jeudi 26 janvier 2017 - 10:22:45
Document(s) archivé(s) le : mercredi 26 avril 2017 - 15:50:47

Fichier

 Accès restreint
Fichier visible le : 2019-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Vahid Roostapour, Iman Kiarazm, Mansoor Davoodi. Deterministic Algorithm for 1-Median 1-Center Two-Objective Optimization Problem. Mohammed Taghi Hajiaghayi; Mohammad Reza Mousavi. 1st International Conference on Theoretical Computer Science (TTCS), Aug 2015, Tehran, Iran. Lecture Notes in Computer Science, LNCS-9541, pp.164-178, 2016, Topics in Theoretical Computer Science. 〈10.1007/978-3-319-28678-5_12〉. 〈hal-01446259〉

Partager

Métriques

Consultations de la notice

88