Budget Constrained Minimum Cost Connected Medians

Please always quote using this URN: urn:nbn:de:0297-zib-5783
  • Several practical instances of network design problems require the network to satisfy multiple constraints. In this paper, we address the \emph{Budget Constrained Connected Median Problem}: We are given an undirected graph $G = (V,E)$ with two different edge-weight functions $c$ (modeling the construction or communication cost) and $d$ (modeling the service distance), and a bound~$B$ on the total service distance. The goal is to find a subtree~$T$ of $G$ with minimum $c$-cost $c(T)$ subject to the constraint that the sum of the service distances of all the remaining nodes $v \in V\setminus T$ to their closest neighbor in~$T$ does not exceed the specified budget~$B$. This problem has applications in optical network design and the efficient maintenance of distributed databases. We formulate this problem as bicriteria network design problem, and present bicriteria approximation algorithms. We also prove lower bounds on the approximability of the problem that demonstrate that our performance ratios are close to best possible

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Goran Konjevod, Sven O. Krumke, Madhav Marathe
Document Type:ZIB-Report
Tag:Approximation Algorithms; NP-hardness; Network
MSC-Classification:68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Qxx Theory of computing / 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) [See also 03D15, 68Q17, 68Q19]
68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Qxx Theory of computing / 68Q25 Analysis of algorithms and problem complexity [See also 68W40]
68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Rxx Discrete mathematics in relation to computer science / 68R10 Graph theory (including graph drawing) [See also 05Cxx, 90B10, 90B35, 90C35]
Date of first Publication:2000/03/24
Series (Serial Number):ZIB-Report (00-10)
Published in:Appeared in: Proceedings of the 26th International Workshop on Graph-Theoretic Concepts in Computer Science, Konstanz, Germany, Vol 1928 of Lecture Notes in Computer Science, Springer Jun 2000, 267-278