Budget constrained minimum cost connected medians

DOI10.1016/j.jda.2004.04.006zbMath1118.90017OpenAlexW1990284882MaRDI QIDQ876728

Sven O. Krumke, Madhav V. Marathe, Goran Konjevod

Publication date: 26 April 2007

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2004.04.006

zbMATH Keywords

mediannetwork designapproximation algorithmsNP-hardness\(k\)-median problemgroup Steiner tree problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Continuous location (90B85) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites Work

• Competitive algorithms for distributed data management.
• Geometric algorithms and combinatorial optimization
• Approximation algorithms for the Geometric Covering Salesman Problem
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Bicriteria Network Design Problems
• The Covering Salesman Problem
• Spanning Trees—Short or Small
• Competitive distributed file allocation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Budget constrained minimum cost connected medians