Approximating the generalized minimum Manhattan network problem
type: Item
instance of: scholarly article
title: Approximating the generalized minimum Manhattan network problem
zbMATH Open document ID: 1390.68715
author: Aparna Das
author: Krzysztof Fleszar
author: Joachim Spoerhase
author: Sankar Veeramoni
author: Alexander Wolff
author: Stephen G. Kobourov
published in: Algorithmica
publication date: 2018-05-23T00:00:00Z
full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 6872023
zbMATH Keywords: approximation algorithms
zbMATH Keywords: computational geometry
zbMATH Keywords: minimum Manhattan network
MaRDI profile type: Publication
OpenAlex ID: W155897563
cites work: Small-size ε-nets for axis-parallel rectangles and boxes
cites work: Approximation schemes for NP-hard geometric optimization problems: a survey
cites work: Polynomial time approximation scheme for the rectilinear Steiner arborescence problem
cites work: Almost optimal set covers in finite VC-dimension
cites work: Minimum Manhattan network is NP-complete
cites work: On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
cites work: A rounding algorithm for approximating minimum Manhattan networks
cites work: Approximating the Generalized Minimum Manhattan Network Problem
cites work: Approximating minimum Manhattan networks in higher dimensions
cites work: Improved approximation algorithms for directed Steiner forest
cites work: Q2968082
cites work: GREEDY CONSTRUCTION OF 2-APPROXIMATE MINIMUM MANHATTAN NETWORKS
cites work: Approximating a minimum Manhattan network
cites work: The Minimal Manhattan Network Problem in Three Dimensions
cites work: Geometric Spanner Networks
cites work: Cost-minimal trees in directed acyclic graphs
cites work: The rectilinear Steiner arborescence problem
cites work: The Rectilinear Steiner Arborescence Problem Is NP-Complete
cites work: Q4782696
DOI: 10.1007/S00453-017-0298-0
description: scientific article; zbMATH DE number 6872023