VARIATIONS OF BASE-STATION PLACEMENT PROBLEM ON THE BOUNDARY OF A CONVEX REGION

DOI10.1142/S0129054108005747MaRDI QIDQ3526982zbMATH OpenFDO

Authors Sasanka Roy, Sandip Das, Gautam K. Das, Subhas C. Nandy

Publication date 25 September 2008

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054108005747

zbMATH Keywords

approximation algorithmcomplexitycovering problemwireless network

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Approximation algorithms (68W25) Discrete location and assignment (90B80) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Base station placement on boundary of a convex polygon
• Distributed Computing – IWDC 2005
• Efficient algorithm for placing a given number of base stations to cover a convex region
• scientific article; zbMATH DE number 2089212
• Polynomial time approximation schemes for base station coverage with minimum total radii

Cites work

• A Best Possible Heuristic for the k-Center Problem
• A heuristic for the p-center problem in graphs
• A near-linear algorithm for the planar 2-center problem
• scientific article; zbMATH DE number 1033560 (Why is no real title available?)
• Linear-Time Algorithms for Linear Programming in R^3 and Related Problems
• More planar two-center algorithms
• Polynomial time approximation schemes for base station coverage with minimum total radii
• The searching over separators strategy to solve some NP-hard problems in subexponential time

Cited in

(20)

• The connected disk covering problem
• Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares
• An approximation algorithm for k-center problem on a convex polygon
• Optimal placement of base stations in border surveillance using limited capacity drones
• Range assignment of base-stations maximizing coverage area without interference
• Solving the natural wireless localization problem to optimality efficiently
• The Euclidean \(k\)-supplier problem in \(I R^2\)
• scientific article; zbMATH DE number 1629974 (Why is no real title available?)
• THE ALIGNED K-CENTER PROBLEM
• scientific article; zbMATH DE number 2089212 (Why is no real title available?)
• Base station placement on boundary of a convex polygon
• Base Location Problems for Base-Monotone Regions
• Distributed Computing – IWDC 2005
• Constrained k-center problem on a convex polygon
• Covering convex polygons by two congruent disks
• Covering convex polygons by two congruent disks
• Worst-case optimal covering of rectangles by disks
• Worst-case optimal covering of triangles by disks
• Efficient algorithm for placing a given number of base stations to cover a convex region
• An incremental version of the \(k\)-center problem on boundary of a convex polygon

Describes a project that uses

Uses Software

• LEDA

This page was built for publication: VARIATIONS OF BASE-STATION PLACEMENT PROBLEM ON THE BOUNDARY OF A CONVEX REGION

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