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

DOI10.1142/S0129054108005747zbMath1155.68015MaRDI QIDQ3526982

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

Publication date: 25 September 2008

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

zbMATH Keywords

complexityapproximation algorithmwireless networkcovering problem

Mathematics Subject Classification ID

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

Related Items

The Euclidean \(k\)-supplier problem in \(I R^2\), An incremental version of the \(k\)-center problem on boundary of a convex polygon, The connected disk covering problem, THE ALIGNED K-CENTER 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, Covering convex polygons by two congruent disks, Constrained k-Center Problem on a Convex Polygon, Covering convex polygons by two congruent disks

Uses Software

• LEDA

Cites Work

• Unnamed Item
• A heuristic for the p-center problem in graphs
• A near-linear algorithm for the planar 2-center problem
• More planar two-center algorithms
• The searching over separators strategy to solve some NP-hard problems in subexponential time
• Polynomial time approximation schemes for base station coverage with minimum total radii
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• A Best Possible Heuristic for the k-Center Problem