Guarding 1.5D terrains with demands

DOI10.1080/00207160.2012.707800MaRDI QIDQ4902836zbMATH OpenOpenAlexFDO

Authors Domagoj Matijević, Domagoj Ševerdija, Khaled Elbassioni

Publication date 18 January 2013

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/00207160.2012.707800

zbMATH Keywords

approximation algorithmtotally balanced matricesLP relaxation1.5D terrain guardingdemands

Mathematics Subject Classification ID

Linear programming (90C05) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• Improved approximations for guarding 1.5-dimensional terrains
• Improved approximations for guarding 1.5-dimensional terrains
• A Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
• A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains
• A constant-factor approximation algorithm for optimal terrain guarding

Cites work

• scientific article; zbMATH DE number 6297811 (Why is no real title available?)
• A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains
• A Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
• An Approximation Scheme for Terrain Guarding
• Approximation Algorithms for Rectangle Stabbing and Interval Stabbing Problems
• Improved approximation algorithms for geometric set cover
• Improved approximations for guarding 1.5-dimensional terrains
• On the set multicover problem in geometric settings
• PTAS for geometric hitting set problems via local search

Cited in

(6)

• Improved approximations for guarding 1.5-dimensional terrains
• A finite dominating set of cardinality \(O(k)\) and a witness set of cardinality \(O(n)\) for 1.5D terrain guarding problem
• Improved approximations for guarding 1.5-dimensional terrains
• A Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
• Guarding a terrain by two watchtowers
• scientific article; zbMATH DE number 6297811 (Why is no real title available?)

This page was built for publication: Guarding 1.5D terrains with demands

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