A finite dominating set of cardinality \(O(k)\) and a witness set of cardinality \(O(n)\) for 1.5D terrain guarding problem

DOI10.1007/s10479-017-2432-4zbMath1369.90094OpenAlexW2588706166MaRDI QIDQ2400004

Haluk Eliş

Publication date: 25 August 2017

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

Full work available at URL: https://doi.org/10.1007/s10479-017-2432-4

zbMATH Keywords

finite dominating setslocationzero-one integer programmingterrain guarding problem

Mathematics Subject Classification ID

Integer programming (90C10) Discrete location and assignment (90B80)

Cites Work

• Unnamed Item
• Improved approximations for guarding 1.5-dimensional terrains
• Guarding polyhedral terrains
• Filtering policies in loss queueing network location problems
• Improved approximation algorithms for geometric set cover
• Planar Weber location problems with barriers and block norms
• Approximation algorithms for terrain guarding.
• Terrain Guarding is NP-Hard
• A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains
• An Approximation Scheme for Terrain Guarding
• Finite Dominating Sets for Network Location Problems
• Guarding 1.5D terrains with demands
• A Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
• Solving nonconvex planar location problems by finite dominating sets

This page was built for publication: A finite dominating set of cardinality \(O(k)\) and a witness set of cardinality \(O(n)\) for 1.5D terrain guarding problem