A General Approximation Technique for Constrained Forest Problems
From MaRDI portal
Publication:4834382
DOI10.1137/S0097539793242618zbMath0834.68055WikidataQ56474462 ScholiaQ56474462MaRDI QIDQ4834382
David P. Williamson, Michel X. Goemans
Publication date: 18 March 1996
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)
Related Items
An Improved Approximation Algorithm for the Matching Augmentation Problem, From Cost Sharing Mechanisms to Online Selection Problems, A survey of variants and extensions of the location-routing problem, Approximating Steiner Trees and Forests with Minimum Number of Steiner Points, Routing Under Uncertainty: The a priori Traveling Repairman Problem, Primal-dual approximation algorithms for feedback problems in planar graphs, Energy-Efficient Communication in Multi-interface Wireless Networks, Locating leak detecting sensors in a water distribution network by solving prize-collecting Steiner arborescence problems, The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online, Minimum-Cost Network Design with (Dis)economies of Scale, Linear-Time Approximation for Maximum Weight Matching, Chvátal-Gomory cuts for the Steiner tree problem, Improved Approximation Algorithms for (Budgeted) Node-weighted Steiner Problems, Minimum‐weight subgraphs with unicyclic components and a lower‐bounded girth, Exact and Approximation Algorithms for the Expanding Search Problem, Combinatorial Heuristics for Inventory Routing Problems, On the Exact Solution of Prize-Collecting Steiner Tree Problems, On the Integrality Gap of the Prize-Collecting Steiner Forest LP, The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem, A Spectral Approach to Network Design, The restricted Chinese postman problems with penalties, Approximation algorithms for Steiner forest: An experimental study, Solving the prize‐collecting Euclidean Steiner tree problem, FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM, Solving Steiner trees: Recent advances, challenges, and perspectives, Primal-Dual Schema for Capacitated Covering Problems, Approximation algorithms for prize-collecting capacitated network design problems, Minimum-Weight Cycle Covers and Their Approximability, A unified approach to approximate partial, prize-collecting, and budgeted sweep cover problems, Improved approximation algorithm for the asymmetric prize-collecting TSP, Unnamed Item, Prize-collecting asymmetric traveling salesman problem admits polynomial time approximation within a constant ratio, Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem, Locating service and charging stations, Approximation algorithms for the restricted \(k\)-Chinese postman problems with penalties, LP-Based Algorithms for Capacitated Facility Location, Unnamed Item, Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems, A RELAX-AND-CUT ALGORITHM FOR THE KNAPSACK NODE WEIGHTED STEINER TREE PROBLEM, A PTAS for the Steiner Forest Problem in Doubling Metrics, A Dual Ascent-Based Branch-and-Bound Framework for the Prize-Collecting Steiner Tree and Related Problems, Unnamed Item, A Local-Search Algorithm for Steiner Forest, Strong Steiner Tree Approximations in Practice, Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow, LP Relaxation and Tree Packing for Minimum $k$-Cut, Fast and Deterministic Approximations for k-Cut., An Exact Algorithm for the Steiner Forest Problem, An O(logn)-Competitive Algorithm for Online Constrained Forest Problems, On Variants of File Caching, Upgrading bottleneck constrained forests, Online Node-weighted Steiner Forest and Extensions via Disk Paintings, Supply Chain Management with Online Customer Selection, Unnamed Item, Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints, Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements, 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, Approximating \(k\)-forest with resource augmentation: a primal-dual approach, Approximating node-weighted \(k\)-MST on planar graphs, Relaxations of Combinatorial Problems Via Association Schemes, Improved approximations for two-stage MIN-cut and shortest path problems under uncertainty, Approximating Steiner Networks with Node Weights, Hallucination Helps: Energy Efficient Virtual Circuit Routing, Unnamed Item, Clustering with Internal Connectedness, Designing Networks with Good Equilibria under Uncertainty, Primal-Dual Schema and Lagrangian Relaxation for the k-Location-Routing Problem, On the Complexity of Local Graph Transformations, Prize-Collecting TSP with a Budget Constraint, Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems, Improved Primal-Dual Approximation Algorithm for the Connected Facility Location Problem, Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree, Unnamed Item, Unnamed Item, Unnamed Item, A 2-approximation for the \(k\)-prize-collecting Steiner tree problem, Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique, A 2.5-factor approximation algorithm for the \(k\)-MST problem, Beyond Moulin mechanisms, On-line generalized Steiner problem, An approximation algorithm for the generalized prize-collecting Steiner forest problem with submodular penalties, Approximation and complexity of multi-target graph search and the Canadian traveler problem, Primal-dual approximation algorithms for the prize-collecting Steiner tree problem, A primal-dual approximation algorithm for a two depot heterogeneous traveling salesman problem, Dynamic algorithms via the primal-dual method, Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing, Network repair crew scheduling and routing for emergency relief distribution problem, Constant-approximation for prize-collecting min-sensor sweep coverage with base stations, A survey of combinatorial optimization problems in multicast routing, Approximation schemes for node-weighted geometric Steiner tree problems, Minimizing submodular functions over families of sets, Using fractional primal-dual to schedule split intervals with demands, A simple LP-based approximation algorithm for the matching augmentation problem, Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem, New primal-dual algorithms for Steiner tree problems, Approximation algorithm for prize-collecting sweep cover with base stations, An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties, A PTAS for the geometric connected facility location problem, A 4-approximation algorithm for \(k\)-prize collecting Steiner tree problems, Thresholded covering algorithms for robust and max-min optimization, A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem, The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm, Strategic cooperation in cost sharing games, Improved approximation algorithms for directed Steiner forest, Approximation algorithms and hardness results for labeled connectivity problems, A survey of the standard location-routing problem, An approximation algorithm for the generalized \(k\)-multicut problem, A primal-dual approximation algorithm for the asymmetric prize-collecting TSP, Euclidean prize-collecting Steiner forest, Graph coloring with rejection, Energy-efficient communication in multi-interface wireless networks, Improved solution to data gathering with mobile mule, A primal-dual algorithm for the generalized prize-collecting Steiner forest problem, Complexity and approximation for traveling salesman problems with profits, On the complexity of graph tree partition problems., Approximation algorithms for supply chain planning and logistics problems with market choice, Connected facility location via random facility sampling and core detouring, A primal-dual approximation algorithm for the vertex cover \(P^3\) problem, Approximation algorithm for minimizing total latency in machine scheduling with deliveries, Polyhedral study of the connected subgraph problem, Approximating max-min weighted \(T\)-joins, An approximation algorithm for network design problems with downwards-monotone demand functions, A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching, Stronger MIP formulations for the Steiner forest problem, Black-box reductions for cost-sharing mechanism design, Approximating \(k\)-generalized connectivity via collapsing HSTs, Online covering salesman problem, A simpler and better derandomization of an approximation algorithm for single source rent-or-buy, Primal-dual approximation algorithms for integral flow and multicut in trees, An approximation algorithm for minimum-cost vertex-connectivity problems, Weighted matching with pair restrictions, Online unit clustering: Variations on a theme, An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem, Online constrained forest and prize-collecting network design, Local search algorithms for the red-blue median problem, Elementary approximation algorithms for prize collecting Steiner tree problems, The online prize-collecting traveling salesman problem, The Steiner forest problem revisited, A better approximation algorithm for the budget prize collecting tree problem., Complexity and approximation of the constrained forest problem, A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem, A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs, The A priori traveling repairman problem, Clustering with lower-bounded sizes. A general graph-theoretic framework, Approximation of Steiner forest via the bidirected cut relaxation, Maximum rooted connected expansion, Approximating Steiner trees and forests with minimum number of Steiner points, A new formulation for the traveling deliveryman problem, Approximation algorithms for group prize-collecting and location-routing problems, Approximation algorithms for the connected sensor cover problem, An approximation algorithm to the \(k\)-Steiner forest problem, Primal-dual schema for capacitated covering problems, Approximation algorithms for connected facility location problems, Non-cooperative tree creation, Path hitting in acyclic graphs, Approximation algorithms for minimum tree partition, Two-level hub Steiner trees, Approximation algorithms for soft-capacitated facility location in capacitated network design, Minimum-weight cycle covers and their approximability, Recent results on approximating the Steiner tree problem and its generalizations, Parameterized analysis of the online priority and node-weighted Steiner tree problems, A simple rounding scheme for multistage optimization, A 6.55 factor primal-dual approximation algorithm for the connected facility location problem, 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, A 3/2-approximation algorithm for some minimum-cost graph problems, Improved methods for approximating node weighted Steiner trees and connected dominating sets., Approximating minimum-cost connected \(T\)-joins, Online file caching with rejection penalties, A primal-dual approximation algorithm for the survivable network design problem in hypergraphs, Approximating the maximum quadratic assignment problem, Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties, On fixed cost \(k\)-flow problems, Serving rides of equal importance for time-limited dial-a-ride, LP-based algorithms for multistage minimization problems
