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)- Approximation algorithms for Steiner forest: An experimental study
- On the Exact Solution of Prize-Collecting Steiner Tree Problems
- Parameterized analysis of the online priority and node-weighted Steiner tree problems
- scientific article; zbMATH DE number 742977 (Why is no real title available?)
- Approximation algorithms for prize-collecting capacitated network design problems
- Improved approximation algorithms for (budgeted) node-weighted Steiner problems
- On-line generalized Steiner problem
- Approximating the maximum weight cycle/path partition in graphs with weights one and two
- On fixed cost k-flow problems
- Online Node-weighted Steiner Forest and Extensions via Disk Paintings
- Elementary approximation algorithms for prize collecting Steiner tree problems
- Online unit clustering: Variations on a theme
- Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree
- Relaxations of combinatorial problems via association schemes
- Approximation algorithm for minimizing total latency in machine scheduling with deliveries
- Supply chain management with online customer selection
- An approximation algorithm for minimum-cost vertex-connectivity problems
- Online file caching with rejection penalties
- Using fractional primal-dual to schedule split intervals with demands
- The Steiner forest problem revisited
- Improved approximation algorithms for covering pliable set families and flexible graph connectivity
- Approximating Steiner trees and forests with minimum number of Steiner points
- Prize-collecting TSP with a budget constraint
- Cost-effective designs of fault-tolerant access networks in communication systems
- Approximation algorithms for supply chain planning and logistics problems with market choice
- A primal-dual approximation algorithm for the vertex cover P^3 problem
- Approximating Steiner trees and forests with minimum number of Steiner points
- Solving the prize‐collecting Euclidean Steiner tree problem
- Black-box reductions for cost-sharing mechanism design
- On the restricted Steiner multi cycle problem
- Path hitting in acyclic graphs
- Improved approximation algorithms for directed Steiner forest
- Serving rides of equal importance for time-limited dial-a-ride
- Stronger MIP formulations for the Steiner forest problem
- Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing
- A better approximation algorithm for the budget prize collecting tree problem.
- Minimum-cost network design with (dis)economies of scale
- Streaming algorithms for geometric Steiner forest
- A 3/2-approximation algorithm for some minimum-cost graph problems
- A unified approach to approximate partial, prize-collecting, and budgeted sweep cover problems
- Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique
- The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
- Complexity and approximation of the constrained forest problem
- Approximation algorithms for minimum tree partition
- Complexity and approximation for traveling salesman problems with profits
- Chvátal-Gomory cuts for the Steiner tree problem
- Online covering salesman problem
- Single-sink fractionally subadditive network design
- A survey of combinatorial optimization problems in multicast routing
- An approximation algorithm for the generalized k-multicut problem
- Upgrading bottleneck constrained forests
- Recent results on approximating the Steiner tree problem and its generalizations
- Hallucination helps: energy efficient virtual circuit routing
- Online constrained forest and prize-collecting network design
- Approximating max-min weighted \(T\)-joins
- A constant-factor approximation algorithm for the \(k\)-MST problem
- Primal-dual approximation algorithms for feedback problems in planar graphs
- A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs
- Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions
- The power of deferral: maintaining a constant-competitive Steiner tree online
- Minimum-Weight Cycle Covers and Their Approximability
- A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem
- An O( n)-competitive algorithm for online constrained forest problems
- Thresholded covering algorithms for robust and max-min optimization
- Clustering with lower-bounded sizes. A general graph-theoretic framework
- The A priori traveling repairman problem
- A 2.5-factor approximation algorithm for the k-MST problem
- Primal-dual schema for capacitated covering problems
- A PTAS for the Steiner forest problem in doubling metrics
- Approximation and complexity of multi-target graph search and the Canadian traveler problem
- The unbounded integrality gap of a semidefinite relaxation of the traveling salesman problem
- Beyond Moulin mechanisms
- Greedy algorithms for online survivable network design
- Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties
- An Improved Approximation Algorithm for the Matching Augmentation Problem
- An approximation algorithm for the generalized prize-collecting Steiner forest problem with submodular penalties
- Probabilistic models for the Steiner tree problem
- A new formulation for the traveling deliveryman problem
- Approximation algorithms for soft-capacitated facility location in capacitated network design
- A dual ascent-based branch-and-bound framework for the prize-collecting Steiner tree and related problems
- A 6.55 factor primal-dual approximation algorithm for the connected facility location problem
- Approximability of unsplittable shortest path routing problems
- Approximation algorithms for node-weighted directed Steiner problems
- Maximizing rides served for dial-a-ride on the uniform metric
- Dynamic algorithms via the primal-dual method
- An approximation algorithm to the \(k\)-Steiner forest problem
- Improved Primal-Dual Approximation Algorithm for the Connected Facility Location Problem
- Approximating the maximum quadratic assignment problem
- A RELAX-AND-CUT ALGORITHM FOR THE KNAPSACK NODE WEIGHTED STEINER TREE PROBLEM
- Exact and Approximation Algorithms for the Expanding Search Problem
- Extending the primal-dual 2-approximation algorithm beyond uncrossable set families
- A better-than-1.6-approximation for prize-collecting TSP
- Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem
- Locating service and charging stations
- A primal-dual approximation algorithm for a two depot heterogeneous traveling salesman problem
- Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem
- A primal-dual approximation algorithm for the survivable network design problem in hypergraphs
- A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem
- On the complexity of graph tree partition problems.
- Maximum rooted connected expansion
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)
