Improved Approximation for Guarding Simple Galleries from the Perimeter

References

Page 1

	Year	Citations
A threshold of ln <i>n</i> for approximating set cover Uriel Feige Journal of the ACM Theory Of ComputingK SubsetsEngineeringPossible SubsetsLower Bound	1998	3.1K
A Greedy Heuristic for the Set-Covering Problem Vašek Chvátal Mathematics of Operations Research Mathematical ProgrammingX BinaryTotal UnimodularityEngineeringBinary Matrix	1979	2.5K
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities Vladimir Vapnik, Alexey Chervonenkis Theory of Probability and Its Applications EngineeringEntropyImprecise ProbabilityProbabilistic ComputationStatistical Inference	1971	2.4K
Learnability and the Vapnik-Chervonenkis dimension Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, Journal of the ACM Artificial IntelligenceEngineeringMachine LearningAlgorithmic LearningComputational Complexity	1989	1.8K
A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP Ran Raz Np ShareNuclear PhysicsData ScienceIsrael Weizmann Inst.Engineering	1997	830
Almost optimal set covers in finite VC-dimension Hervé Brönnimann, Michael T. Goodrich Discrete & Computational Geometry Extremal Set TheorySet-theoretic TopologyExtremal CombinatoricsCombinatorial OptimizationOptimal Set Covers	1995	445
Computational complexity of art gallery problems D. Lee, A. Lin IEEE Transactions on Information Theory Geometric Graph TheoryArt GalleryGraph TheorySimple PolygonEngineering	1986	404
Some NP-hard polygon decomposition problems Joseph O’Rourke, Kenneth J. Supowit IEEE Transactions on Information Theory Mathematical ProgrammingGeometric ModelingPolygon Decomposition ProblemsSpiral SubsetsEngineering	1983	201
Inapproximability Results for Guarding Polygons and Terrains Stephan Eidenbenz, Christoph Stamm, Peter Widmayer Algorithmica Hardware SecurityEngineeringInapproximability ResultsInformation SecurityPerimeter Security	2001	136
The art gallery theorem: its variations, applications and algorithmic aspects Alok Aggarwal Art HistoryContemporary ArtEngineeringGeometric AlgorithmAlgorithm Design	1984	130

Page 1