2-medians in trees with pos/neg weights
type: Item
instance of: scholarly article
title: 2-medians in trees with pos/neg weights
zbMATH Open document ID: 0986.90017
DOI: 10.1016/S0166-218X(00)00177-3
author: Rainer E. Burkard
author: Eranda Çela
author: Helidon Dollani
published in: Discrete Applied Mathematics
publication date: 2001-02-27T00:00:00Z
review text: Consider the positive/negative 2-median problem on a tree of \(n\) vertices. The authors give an \(O(n^2)\) algorithm to solve the problem when the objective function is given as the sum of the minima of the weighted distances between vertices of the tree and facilities, and an \(O(n^3)\) algorithm to solve the problem when the objective function is given as the sum of the weighted minima of the distances between vertices of the tree and facilities.
Mathematics Subject Classification ID: 90B80
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 1512445
zbMATH Keywords: location problem
zbMATH Keywords: median problem
zbMATH Keywords: obnoxious facilities
MaRDI profile type: Publication
cites work: Dynamic and static algorithms for optimal placement of resources in a tree
cites work: A linear algorithm for the pos/neg-weighted 1-median problem on a cactus
cites work: Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
cites work: Improved complexity bounds for location problems on the real line
cites work: Off-Line Maintenance of Planar Configurations
cites work: An Algorithmic Approach to Network Location Problems. II: Thep-Medians
cites work: On the Complexity of Some Common Geometric Location Problems
cites work: Q3358523
cites work: Worst-Case and Probabilistic Analysis of a Geometric Location Problem
cites work: Obnoxious Facility Location on Graphs
cites work: An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
full work available at URL: s0166-218x(00)00177-3
OpenAlex ID: W2029412688
Recommended article: Efficient computation of 2-medians in a tree network with positive/negative weights
Recommended article: The pos/neg-weighted 2-medians in balanced trees with subtree-shaped customers
Recommended article: Efficient algorithms for finding <scp>2‐medians</scp> of a tree
Recommended article: Q4474142
Recommended article: Reverse 2-median problem on trees
Recommended article: Computing the 2‐median on tree networks in O(n lg n) time
Recommended article: On Parametric Medians of Trees
Recommended article: The balanced 2-median and 2-maxian problems on a tree
Recommended article: The median procedure for n-trees
description: scientific article; zbMATH DE number 1512445