Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing
type: Item
instance of: scholarly article
title: Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing
zbMATH Open document ID: 1194.68263
author: Danny Segev
author: Gil Segev
published in: Algorithmica
publication date: 2010-02-23T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 5674260
zbMATH Keywords: approximation algorithms
zbMATH Keywords: Lagrangian relaxation
zbMATH Keywords: Steiner forest
zbMATH Keywords: dense \(k\)-subgraph
MaRDI profile type: Publication
full work available at URL: s00453-008-9189-8
OpenAlex ID: W2170451311
cites work: When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
cites work: Q5501312
cites work: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
cites work: A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem
cites work: Proof verification and the hardness of approximation problems
cites work: Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
cites work: Euclidean distortion and the sparsest cut
cites work: Greedily Finding a Dense Subgraph
cites work: An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
cites work: New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
cites work: On-line generalized Steiner problem
cites work: Using homogeneous weights for approximating the partial cover problem
cites work: Q4527000
cites work: A note on the prize collecting traveling salesman problem
cites work: A constant-factor approximation algorithm for the \(k\)-MST problem
cites work: Approximation Algorithms for Directed Steiner Problems
cites work: Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
cites work: Q3579405
cites work: Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
cites work: Cut problems in graphs with a budget constraint
cites work: Approximation algorithms for maximization problems arising in graph partitioning
cites work: The dense \(k\)-subgraph problem
cites work: Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree
cites work: On approximation of the submodular set cover problem
cites work: Approximation algorithms for partial covering problems
cites work: Q4198056
cites work: Saving an epsilon
cites work: A General Approximation Technique for Constrained Forest Problems
cites work: Approximating the k-multicut problem
cites work: Automata, Languages and Programming
cites work: Dial a Ride from k-Forest
cites work: The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
cites work: An improved rounding method and semidefinite programming relaxation for graph partition
cites work: An Efficient Polynomial Time Approximation Scheme for the Constrained Minimum Spanning Tree Problem Using Matroid Intersection
cites work: Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
cites work: A Unified Approach to Approximating Partial Covering Problems
cites work: Partial multicuts in trees
cites work: The geometry of graphs and some of its algorithmic applications
cites work: Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
cites work: Real-time scheduling with a budget
cites work: Optimization, approximation, and complexity classes
cites work: Spanning Trees—Short or Small
cites work: A Tight Analysis of the Greedy Algorithm for Set Cover
DOI: 10.1007/S00453-008-9189-8
description: scientific article; zbMATH DE number 5674260