A General Approximation Technique for Constrained Forest Problems
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 742977
- Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems
- scientific article; zbMATH DE number 1445376
- Elementary approximation algorithms for prize collecting Steiner tree problems
- Approximating minimum-cost graph problems with spanning tree edges
Cited in
(only showing first 100 items - show all)- A new formulation for the traveling deliveryman problem
- Approximation algorithms for group prize-collecting and location-routing problems
- An approximation algorithm to the \(k\)-Steiner forest problem
- Approximation algorithms for connected facility location problems
- Non-cooperative tree creation
- Path hitting in acyclic graphs
- Approximation algorithms for soft-capacitated facility location in capacitated network design
- Minimum-weight cycle covers and their approximability
- A 6.55 factor primal-dual approximation algorithm for the connected facility location problem
- Approximation algorithms for minimum tree partition
- An efficient approximation algorithm for the survivable network design problem
- An improved approximation ratio for the minimum latency problem
- A constant-factor approximation algorithm for the \(k\)-MST problem
- On the complexity of graph tree partition problems.
- Recent results on approximating the Steiner tree problem and its generalizations
- Approximating the maximum quadratic assignment problem
- Approximation and complexity of multi-target graph search and the Canadian traveler problem
- Dynamic algorithms via the primal-dual method
- A survey of the standard location-routing problem
- A primal-dual algorithm for the generalized prize-collecting Steiner forest problem
- Black-box reductions for cost-sharing mechanism design
- Online covering salesman problem
- Weighted matching with pair restrictions
- An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem
- Online constrained forest and prize-collecting network design
- Approximating Steiner trees and forests with minimum number of Steiner points
- Improved methods for approximating node weighted Steiner trees and connected dominating sets.
- A primal-dual approximation algorithm for the survivable network design problem in hypergraphs
- On-line generalized Steiner problem
- Minimizing submodular functions over families of sets
- Strategic cooperation in cost sharing games
- A primal-dual approximation algorithm for the asymmetric prize-collecting TSP
- Energy-efficient communication in multi-interface wireless networks
- Connected facility location via random facility sampling and core detouring
- A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs
- Maximum rooted connected expansion
- Two-level hub Steiner trees
- A simple rounding scheme for multistage optimization
- Serving rides of equal importance for time-limited dial-a-ride
- LP-based algorithms for multistage minimization problems
- An approximation algorithm for the generalized prize-collecting Steiner forest problem with submodular penalties
- Constant-approximation for prize-collecting min-sensor sweep coverage with base stations
- A simple LP-based approximation algorithm for the matching augmentation problem
- Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem
- Approximation algorithm for prize-collecting sweep cover with base stations
- An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties
- The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
- Improved solution to data gathering with mobile mule
- Stronger MIP formulations for the Steiner forest problem
- Approximation of Steiner forest via the bidirected cut relaxation
- Parameterized analysis of the online priority and node-weighted Steiner tree problems
- A 3/2-approximation algorithm for some minimum-cost graph problems
- Approximating minimum-cost connected \(T\)-joins
- Online file caching with rejection penalties
- Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties
- Primal-dual approximation algorithms for the prize-collecting Steiner tree problem
- A survey of combinatorial optimization problems in multicast routing
- Approximation schemes for node-weighted geometric Steiner tree problems
- A PTAS for the geometric connected facility location problem
- A 4-approximation algorithm for k-prize collecting Steiner tree problems
- A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem
- Approximation algorithms and hardness results for labeled connectivity problems
- Euclidean prize-collecting Steiner forest
- Complexity and approximation for traveling salesman problems with profits
- Approximating max-min weighted \(T\)-joins
- A simpler and better derandomization of an approximation algorithm for single source rent-or-buy
- A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem
- Improved approximations for two-stage MIN-cut and shortest path problems under uncertainty
- A class of heuristics for the constrained forest problem
- On fixed cost k-flow problems
- A survey of variants and extensions of the location-routing problem
- Locating leak detecting sensors in a water distribution network by solving prize-collecting Steiner arborescence problems
- Chvátal-Gomory cuts for the Steiner tree problem
- The restricted Chinese postman problems with penalties
- Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique
- Relaxations of combinatorial problems via association schemes
- A 2.5-factor approximation algorithm for the k-MST problem
- LP-based algorithms for capacitated facility location
- An O( n)-competitive algorithm for online constrained forest problems
- On variants of file caching
- Cost-effective designs of fault-tolerant access networks in communication systems
- Approximability of unsplittable shortest path routing problems
- Probabilistic models for the Steiner tree problem
- Clustering with internal connectedness
- Primal-dual schema and Lagrangian relaxation for the k-location-routing problem
- A primal-dual approximation algorithm for a two depot heterogeneous traveling salesman problem
- Energy-Efficient Communication in Multi-interface Wireless Networks
- Linear-time approximation for maximum weight matching
- Network repair crew scheduling and routing for emergency relief distribution problem
- LP relaxation and tree packing for minimum k-cut
- From cost sharing mechanisms to online selection problems
- Approximating Steiner trees and forests with minimum number of Steiner points
- Routing under uncertainty: the \textit{a priori} traveling repairman problem
- The power of deferral: maintaining a constant-competitive Steiner tree online
- Minimum-cost network design with (dis)economies of scale
- Primal-Dual Schema for Capacitated Covering Problems
- Minimum-Weight Cycle Covers and Their Approximability
- Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem
- Matching Based Augmentations for Approximating Connectivity Problems
- A RELAX-AND-CUT ALGORITHM FOR THE KNAPSACK NODE WEIGHTED STEINER TREE PROBLEM
This page was built for publication: A General Approximation Technique for Constrained Forest Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4834382)
