Fully polynomial approximation schemes for locating a tree-shaped facility: A generalization of the knapsack problem

DOI10.1016/S0166-218X(98)00059-6zbMath0910.90241OpenAlexW2052548593WikidataQ126297015 ScholiaQ126297015MaRDI QIDQ1270784

Arie Tamir

Publication date: 3 November 1998

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

knapsack problemNP-hardfacility locationsubtreefully polynomial approximation schemesTamirtree-shaped facility

Mathematics Subject Classification ID

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

Related Items

A quadratic time exact algorithm for continuous connected 2-facility location problem in trees, Extensive facility location problems on networks: an updated review, Revisiting \(k\)-sum optimization, Locating a discrete subtree of minimum variance on trees: new strategies to tackle a very hard problem, Finding the conditional location of a median path on a tree, Locating tree-shaped facilities using the ordered median objective, Range minimization problems in path-facility location on trees, The continuous and discrete path‐variance problems on trees, Extensive facility location problems on networks with equity measures, The centdian subtree on tree networks, Improved algorithms for single machine scheduling with release dates and rejections

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation algorithms for the capacitated plant allocation problem
• On locating path- or tree-shaped facilities on networks
• Maximal Direct Covering Tree Problems
• The optimal location of a path or tree in a tree network
• Fast Approximation Algorithms for Knapsack Problems
• An Algorithm for Large Zero-One Knapsack Problems
• Obnoxious Facility Location on Graphs
• On a tree-shaped facility location problem of Minieka
• `` Strong NP-Completeness Results
• Combinatorial Problems: Reductibility and Approximation
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees