Deterministic sampling algorithms for network design

DOI10.1007/s00453-009-9344-xzbMath1216.68345OpenAlexW4233380597MaRDI QIDQ547282

Anke van Zuylen

Publication date: 1 July 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9344-x

zbMATH Keywords

network designapproximation algorithmsderandomization

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Approximation algorithms (68W25)

Related Items (7)

Routing Under Uncertainty: The a priori Traveling Repairman Problem ⋮ Approximation algorithms for the a priori traveling repairman ⋮ A priori TSP in the Scenario Model ⋮ A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design ⋮ The A priori traveling repairman problem ⋮ A priori TSP in the scenario model ⋮ A constant approximation algorithm for the uniform a priori capacitated vehicle routing problem with unit demands

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Survivable networks, linear programming relaxations and the parsimonious property
• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Primal-dual algorithms for connected facility location problems
• A simpler and better derandomization of an approximation algorithm for single source rent-or-buy
• Cost-sharing mechanisms for network design
• Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree
• Approximation Algorithms for Metric Facility Location Problems
• A Constant Approximation Algorithm for the a priori Traveling Salesman Problem
• New Approaches for Virtual Private Network Design
• Pricing Tree Access Networks with Connected Backbones
• Deterministic Sampling Algorithms for Network Design
• Approximation via cost sharing
• Boosted sampling
• Simpler and better approximation algorithms for network design
• Heuristic analysis, linear programming and branch and bound
• Local search heuristic for k-median and facility location problems
• A constant factor approximation for the single sink edge installation problems
• Improved Approximation for Single-Sink Buy-at-Bulk
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Improved Primal-Dual Approximation Algorithm for the Connected Facility Location Problem
• A tight bound on approximating arbitrary metrics by tree metrics

This page was built for publication: Deterministic sampling algorithms for network design