Improved complexity results for several multifacility location problems on trees

DOI10.1007/S10479-011-0905-4zbMATH Open1233.90212OpenAlexW1992072336MaRDI QIDQ763099FDOQ763099

Authors: Jörg Kalcsics 

Publication date: 9 March 2012

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-011-0905-4

Recommendations

• Multifacility ordered median problems on networks: A further analysis
• An O\((nm)\) algorithm for a special case of the multimedian location problem on a tree
• Locating tree-shaped facilities using the ordered median objective
• The \(k\)-centrum multi-facility location problem
• Medi-Centers of a Tree

zbMATH Keywords

dynamic programmingordered median problemtree networksmultifacility location problems

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Discrete location and assignment (90B80)

Cites Work

• Location theory. A unified approach
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Slowing down sorting networks to obtain faster sorting algorithms
• Algorithmic results for ordered median problems
• An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
• The \(k\)-centrum multi-facility location problem
• Multifacility ordered median problems on networks: A further analysis
• Improved complexity bounds for location problems on the real line
• New Results on the Complexity of p-Centre Problems
• Title not available (Why is that?)
• A polynomial algorithm for thep-centdian problem on a tree
• On the exponential cardinality of FDS for the ordered \(p\)-median problem
• Title not available (Why is that?)

Cited In (12)

• Locating tree-shaped facilities using the ordered median objective
• Multifacility ordered median problems on networks: A further analysis
• The \(k\)-centrum multi-facility location problem
• On the complexity of the regenerator location problem treewidth and other parameters
• Title not available (Why is that?)
• MULTI-FACILITY LOCATION PROBLEM WITH NONINCREASING PIECEWISE LINEAR DEMAND ON A TREE
• An O\((nm)\) algorithm for a special case of the multimedian location problem on a tree
• Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees
• Improved Complexity Bounds for Center Location Problems on Networks by Using Dynamic Data Structures
• The generalized P‐forest problem on a tree network
• Revisiting \(k\)-sum optimization
• Fair optimization and networks: a survey

This page was built for publication: Improved complexity results for several multifacility location problems on trees

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