Deterministic sampling algorithms for network design

DOI10.1007/s00453-009-9344-xzbMath1216.68345MaRDI 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 design; approximation algorithms; derandomization

Mathematics Subject Classification ID

68M10: Network design and communication in computer systems

68W25: Approximation algorithms

Related Items

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item