A deterministic algorithm for the cost-distance problem

MaRDI QIDQ2768299zbMATH OpenFDO

Authors Chandra Chekuri, Sanjeev Khanna, Joseph (Seffi) Naor

Publication date 29 July 2003

zbMATH Keywords

cost-distance network design problemLagrangean relaxationundirected graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35)

Recommendations

• Cost-Distance: Two Metric Network Design
• Budget constrained minimum cost connected medians
• scientific article; zbMATH DE number 1696540
• scientific article; zbMATH DE number 1532274
• scientific article; zbMATH DE number 2080990

Cited in

(15)

• Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees
• Online covering with \(\ell_q\)-norm objectives and applications to network design
• Minimizing the sum of distances to a server in a constraint network
• A Deterministic Reduction for the Gap Minimum Distance Problem
• Cost-Distance: Two Metric Network Design
• LP-based approximation algorithms for facility location in buy-at-bulk network design
• An explicit bound on the transportation cost distance
• Improved approximation algorithms for directed Steiner forest
• Online Buy-at-Bulk Network Design
• An efficient algorithm for computing free distance (Corresp.)
• Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph
• On the complexity of the cable-trench problem
• LP-based approximation algorithms for facility location in buy-at-bulk network design
• Buy-at-bulk facility location on trees
• Approximation algorithms for hop constrained and buy-at-bulk network design via hop constrained oblivious routing

This page was built for publication: A deterministic algorithm for the cost-distance problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2768299)