Approximation algorithms for the connected sensor cover problem
From MaRDI portal
Publication:2290655
DOI10.1016/j.tcs.2020.01.020zbMath1436.68383arXiv1505.00081OpenAlexW773348653WikidataQ126331152 ScholiaQ126331152MaRDI QIDQ2290655
Qicai Shi, Jian Li, Lingxiao Huang
Publication date: 29 January 2020
Published in: Theoretical Computer Science, Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1505.00081
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Functional programming and lambda calculus (68N18) Approximation algorithms (68W25) Wireless sensor networks as related to computer science (68M18)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Connected dominating set. Theory and applications
- The relation of connected set cover and group Steiner tree
- Complexity and approximation of the connected set-cover problem
- New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs
- Improved approximation algorithms for geometric set cover
- A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph
- A better constant-factor approximation for weighted dominating set in unit disk graph
- Hitting sets when the VC-dimension is small
- Improved methods for approximating node weighted Steiner trees and connected dominating sets.
- Almost optimal set covers in finite VC-dimension
- The polymatroid Steiner problems
- A greedy approximation algorithm for the group Steiner problem
- Weighted geometric set cover via quasi-uniform sampling
- The Design of Approximation Algorithms
- A threshold of ln n for approximating set cover
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- A PTAS for the Weighted Unit Disk Cover Problem
- Saving an epsilon
- Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
- New existence proofs ε-nets
- Planar Formulae and Their Uses
- An analysis of approximations for maximizing submodular set functions—I
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
- Simple heuristics for unit disk graphs
- A General Approximation Technique for Constrained Forest Problems
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
- Analytical approach to parallel repetition
- PTAS for geometric hitting set problems via local search
- Analyzing the Optimal Neighborhood: Algorithms for Budgeted and Partial Connected Dominating Set Problems
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- A tight bound on approximating arbitrary metrics by tree metrics
This page was built for publication: Approximation algorithms for the connected sensor cover problem
