147. Approximation algorithm for the weighted connected p-median problem
Invited abstract in session TE-2: Network Optimization, stream Discrete Optimization.
Thursday, 16:45 - 18:15Room: C 103
Authors (first author is the speaker)
| 1. | Miklós Krész
|
| InnoRenew CoE | |
| 2. | Murat Elhüseyni
|
| Department of Information Sciences and Technologies, University of Primorska | |
| 3. | Burak Kocuk
|
| Industrial Engineering, Sabanci University |
Abstract
In this talk we consider a special case of the well-known p-median problem, the weighted connected p-median problem. The connectivity restriction holds for the placed facilities, i.e. they must form span a connected subgraph. Moreover, we are distinguishing two types of costs: the transportation cost is the cost of the traditional p-median problem between the demands and the facilities, whereas the connection cost is the weight of the minimum spanning tree on the facilities. Nevertheless, for the transportation and the connection we use different cost units. The objective is to place the facilities in such a way to minimize the overall costs (transportation and connection costs).
Our goal is to present a bicrtiteria optimization algorithm for the above problem. In this bictiteria framework we will get an upper bound for the approximation ratio with the assumption that the size of the solution is also bounded with respect to the parameter p. We will also present in which way this theoretical result can initiate practical solution heuristics for the problem.
Acknowledgements: The authors gratefully acknowledge the support of the Slovenian Research and Innovation Agency (ARIS) through grants N1-0223 and N2-0171. Miklós Krész has been also supported by the research program CogniCom (0013103) at the University of Primorska.
Keywords
- Linear and nonlinear optimization
Status: accepted
Back to the list of papers