Approximation algorithms for buy-at-bulk geometric network design

DOI10.1142/S0129054111009148MaRDI QIDQ3224959zbMATH OpenOpenAlexFDO

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

Publication date 13 March 2012

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054111009148

zbMATH Keywords

dynamic programmingapproximation algorithmgeometric networksbuy-at-bulkbelt decompositionHanan gridquasi-polynomial-time approximation scheme (QPTAS)

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Deterministic network models in operations research (90B10) Approximation algorithms (68W25)

Recommendations

• Approximation Algorithms for Buy-at-Bulk Geometric Network Design
• Approximation algorithms for nonuniform buy-at-bulk network design
• Approximation algorithms for node-weighted buy-at-bulk network design
• Improved Approximation for Single-Sink Buy-at-Bulk
• Approximating directed buy-at-bulk network design

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A catalog of Hanan grid problems
• A simpler and better derandomization of an approximation algorithm for single source rent-or-buy
• An O ( n log n ) Algorithm for Rectilinear Minimal Spanning Trees
• Approximating the single-sink link-installation problem in network design
• Approximation algorithms for nonuniform buy-at-bulk network design
• Connected facility location via random facility sampling and core detouring
• Discrete cost multicommodity network optimization problems and exact solution methods
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• On Steiner’s Problem with Rectilinear Distance
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Source sink flows with capacity installation in batches

Cited in

(5)

• Approximation schemes for capacitated geometric network design
• Online Buy-at-Bulk Network Design
• Approximation algorithms for node-weighted buy-at-bulk network design
• Approximation Algorithms for Buy-at-Bulk Geometric Network Design
• A New Approximation Algorithm for the Selective Single-Sink Buy-at-Bulk Problem in Network Design

This page was built for publication: Approximation algorithms for buy-at-bulk geometric network design

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