Network design for information networks

MaRDI QIDQ2921761zbMATH OpenFDO

Authors Ara Hayrapetyan, Chaitanya Swamy, Éva Tardos

Publication date 13 October 2014

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Approximation algorithms (68W25) Discrete location and assignment (90B80) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Recommendations

• LP Rounding Approximation Algorithms for Stochastic Network Design
• Automata, Languages and Programming
• Sampling and cost-sharing: approximation algorithms for stochastic optimization problems
• Cost-Distance: Two Metric Network Design
• Stochastic Steiner Tree with Non-uniform Inflation

Cited in

(33)

• A note on the subadditive network design problem
• Approximation and complexity of multi-target graph search and the Canadian traveler problem
• Online constrained forest and prize-collecting network design
• Equivalence of convex minimization problems over base polytopes
• Greedy -approximation algorithm for covering with arbitrary constraints and submodular cost
• A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties
• Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties
• New approximations and hardness results for submodular partitioning problems
• An improved approximation algorithm for squared metric \(k\)-facility location
• An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties
• A primal-dual approximation algorithm for the facility location problem with submodular penalties
• Hedging uncertainty: approximation algorithms for stochastic optimization problems
• Better guarantees for \(k\)-median with service installation costs
• The Submodular Facility Location Problem and the Submodular Joint Replenishment Problem
• Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements
• An approximation algorithm for the risk-adjusted two-stage stochastic facility location problem with penalties
• scientific article; zbMATH DE number 107701 (Why is no real title available?)
• An approximation algorithm for the dynamic facility location problem with submodular penalties
• The price of information in combinatorial optimization
• Approximation algorithm for resource allocation problems with time dependent penalties
• Multi-agent submodular optimization
• Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems
• Traffic-redundancy aware network design
• Approximation algorithms for the fault-tolerant facility location problem with submodular penalties
• A combinatorial approximation algorithm for \(k\)-level facility location problem with submodular penalties
• Algorithm for \(k\)-product facility location problem with submodular penalties
• Approximation algorithm for k-product uncapacitated facility location problem with submodular penalties
• Prize-collecting forest with submodular penalties: improved approximation
• An LP-rounding based algorithm for soft capacitated facility location problem with submodular penalties
• An LP-rounding based algorithm for soft capacitated facility location problem with submodular penalties
• Improved approximation algorithms for the facility location problems with linear/submodular penalties
• Approximation algorithms for the priority facility location problem with penalties
• Elementary approximation algorithms for prize collecting Steiner tree problems

This page was built for publication: Network design for information networks

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