Approximation Algorithms for Buy-at-Bulk Geometric Network Design

DOI10.1007/978-3-642-03367-4_15zbMath1253.68359OpenAlexW2149315855MaRDI QIDQ3183450

Jurek Czyzowicz, Paweł Żyliński, Jesper Jansson, Leszek Gąsieniec, Andrzej Lingas, Artur Czumaj

Publication date: 20 October 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03367-4_15

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)

Related Items

Approximation Schemes for Capacitated Geometric Network Design

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Source sink flows with capacity installation in batches
• Minimum cost capacity installation for multicommodity network flows
• Discrete cost multicommodity network optimization problems and exact solution methods
• Approximating the Single-Sink Link-Installation Problem in Network Design
• A catalog of Hanan grid problems
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Cost-Distance: Two Metric Network Design
• Simpler and better approximation algorithms for network design
• An O ( n log n ) Algorithm for Rectilinear Minimal Spanning Trees
• A constant factor approximation for the single sink edge installation problems
• Algorithm Theory - SWAT 2004
• Improved Approximation for Single-Sink Buy-at-Bulk