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 (only showing first 100 items - show all)
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 ⋮ An improved approximation guarantee for prize-collecting TSP ⋮ 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 ⋮ Modifying networks to obtain low cost trees ⋮ Cluster before you hallucinate: node-capacitated network design and energy efficient routing ⋮ Relaxations of Combinatorial Problems Via Association Schemes ⋮ Improved approximations for two-stage MIN-cut and shortest path problems under uncertainty ⋮ Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions ⋮ Approximating Steiner Networks with Node Weights ⋮ Hallucination Helps: Energy Efficient Virtual Circuit Routing ⋮ Unnamed Item ⋮ What goes around comes around: covering tours and cycle covers with turn costs ⋮ Clustering with Internal Connectedness ⋮ Designing Networks with Good Equilibria under Uncertainty ⋮ Maximizing the number of rides served for time-limited Dial-a-Ride* ⋮ 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
This page was built for publication: A General Approximation Technique for Constrained Forest Problems
