Approximate k-Steiner forests via the Lagrangian relaxation technique with internal preprocessing

DOI10.1007/S00453-008-9189-8zbMATH Open1194.68263OpenAlexW2170451311MaRDI QIDQ848846FDOQ848846

Gil Segev, Danny Segev

Publication date: 23 February 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-008-9189-8

Recommendations

• Approximate k-Steiner Forests Via the Lagrangian Relaxation Technique with Internal Preprocessing
• An Approximation Algorithm to the k-Steiner Forest Problem
• An approximation algorithm to the \(k\)-Steiner forest problem
• scientific article; zbMATH DE number 1757947
• Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation

zbMATH Keywords

approximation algorithmsLagrangian relaxationSteiner forestdense \(k\)-subgraph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Title not available (Why is that?)
• Optimization, approximation, and complexity classes
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• The geometry of graphs and some of its algorithmic applications
• Using homogeneous weights for approximating the partial cover problem
• Approximation algorithms for maximization problems arising in graph partitioning
• Proof verification and the hardness of approximation problems
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• An Efficient Polynomial Time Approximation Scheme for the Constrained Minimum Spanning Tree Problem Using Matroid Intersection
• Approximation algorithms for partial covering problems
• A General Approximation Technique for Constrained Forest Problems
• Approximation Algorithms for Directed Steiner Problems
• Greedily Finding a Dense Subgraph
• The dense \(k\)-subgraph problem
• A note on the prize collecting traveling salesman problem
• Cut problems in graphs with a budget constraint
• Euclidean distortion and the sparsest cut
• New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Saving an epsilon
• Real-time scheduling with a budget
• Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
• An improved rounding method and semidefinite programming relaxation for graph partition
• Spanning Trees—Short or Small
• Approximating the k-multicut problem
• Title not available (Why is that?)
• On approximation of the submodular set cover problem
• Title not available (Why is that?)
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
• A Tight Analysis of the Greedy Algorithm for Set Cover
• Dial a Ride from k-Forest
• Partial multicuts in trees
• Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
• On-line generalized Steiner problem
• Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree
• Automata, Languages and Programming
• Title not available (Why is that?)
• A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem
• A Unified Approach to Approximating Partial Covering Problems
• A constant-factor approximation algorithm for the \(k\)-MST problem

Cited In (3)

• Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
• A 2-approximation algorithm and beyond for the minimum diameter \(k\)-Steiner forest problem
• Approximating \(k\)-forest with resource augmentation: a primal-dual approach

This page was built for publication: Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing

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