Minimum-Cost Network Design with (Dis)economies of Scale

DOI10.1137/110825959zbMath1334.90186OpenAlexW2227904476MaRDI QIDQ3464060

Lisa Zhang, Spyridon Antonakopoulos, Matthew T. Andrews

Publication date: 20 January 2016

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/110825959

zbMATH Keywords

approximation algorithmsdiseconomies of scaleenergy-efficient networks

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Deterministic network models in operations research (90B10) Approximation algorithms (68W25)

Related Items

Energy-efficient scheduling and routing via randomized rounding ⋮ Routing and scheduling for energy and delay minimization in the powerdown model ⋮ Stackelberg pricing games with congestion effects ⋮ A logarithmic approximation for polymatroid congestion games ⋮ Hardness of Routing for Minimizing Superlinear Polynomial Cost in Directed Graphs ⋮ Station assignment with reallocation ⋮ Approximability of Capacitated Network Design ⋮ Hallucination Helps: Energy Efficient Virtual Circuit Routing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combining Exact and Heuristic Approaches for the Capacitated Fixed-Charge Network Flow Problem
• Approximation Algorithms for Nonuniform Buy-at-Bulk Network Design
• Speed scaling to manage energy and temperature
• Approximation via cost sharing
• On non-uniform multicommodity buy-at-bulk network design
• Multicommodity flow, well-linked terminals, and routing problems
• Approximating Some Network Design Problems with Node Costs
• A General Approximation Technique for Constrained Forest Problems
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Cluster before you hallucinate
• Hallucination Helps: Energy Efficient Virtual Circuit Routing
• Computing and Combinatorics
• Edge Disjoint Paths in Moderately Connected Graphs
• Graph partitioning using single commodity flows
• A tight bound on approximating arbitrary metrics by tree metrics
• Bundle-based relaxation methods for multicommodity capacitated fixed charge network design

This page was built for publication: Minimum-Cost Network Design with (Dis)economies of Scale