Deterministic sampling algorithms for network design

DOI10.1007/S00453-009-9344-XzbMATH Open1216.68345OpenAlexW4233380597MaRDI QIDQ547282FDOQ547282

Authors: 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

Recommendations

• Deterministic Sampling Algorithms for Network Design
• Random sampling in cut, flow, and network design problems
• Random sampling in cut, flow, and network design problems
• scientific article; zbMATH DE number 686900
• An exact algorithm for robust network design
• Approximation algorithms for network design problems
• Network design with probabilistic capacities
• THE PROBABILISTIC NETWORK DESIGN PROBLEM
• Perfect sampling for queues and network models

zbMATH Keywords

approximation algorithmsderandomizationnetwork design

Mathematics Subject Classification ID

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

Cites Work

• A tight bound on approximating arbitrary metrics by tree metrics
• Boosted sampling
• Title not available (Why is that?)
• Primal-dual algorithms for connected facility location problems
• Title not available (Why is that?)
• Simpler and better approximation algorithms for network design
• Local search heuristic for k-median and facility location problems
• Improved Primal-Dual Approximation Algorithm for the Connected Facility Location Problem
• Approximation Algorithms for Metric Facility Location Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• A constant factor approximation for the single sink edge installation problems
• Improved Approximation for Single-Sink Buy-at-Bulk
• Title not available (Why is that?)
• Title not available (Why is that?)
• Heuristic analysis, linear programming and branch and bound
• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• An improved approximation algorithm for virtual private network design
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Cost-sharing mechanisms for network design
• Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree
• Approximation via cost sharing
• Survivable networks, linear programming relaxations and the parsimonious property
• A simpler and better derandomization of an approximation algorithm for single source rent-or-buy
• 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, Randomization and Combinatorial Optimization. Algorithms and Techniques

Cited In (13)

• Simpler and better approximation algorithms for network design
• A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design
• Title not available (Why is that?)
• The A priori traveling repairman problem
• Approximation algorithms for the a priori traveling repairman
• Random sampling in cut, flow, and network design problems
• A priori TSP in the scenario model
• A constant approximation algorithm for the uniform a priori capacitated vehicle routing problem with unit demands
• Network design via core detouring for problems without a core
• Deterministic Sampling Algorithms for Network Design
• Pseudorandomness for network algorithms
• Routing Under Uncertainty: The a priori Traveling Repairman Problem
• A priori TSP in the Scenario Model

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

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