Deterministic sampling algorithms for network design
From MaRDI portal
Publication:547282
DOI10.1007/s00453-009-9344-xzbMath1216.68345MaRDI QIDQ547282
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
Related Items
The A priori traveling repairman problem, A priori TSP in the scenario model, A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design, A priori TSP in the Scenario Model, Routing Under Uncertainty: The a priori Traveling Repairman Problem
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
