Guarding 1.5D terrains with demands

DOI10.1080/00207160.2012.707800zbMATH Open1255.90076OpenAlexW2030193964MaRDI QIDQ4902836FDOQ4902836

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

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

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)

Cites Work

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

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
• A Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
• Improved approximations for guarding 1.5-dimensional terrains
• Guarding a terrain by two watchtowers
• Title not available (Why is that?)

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)