Dispersing facilities on planar segment and circle amidst repulsion

Vishwanath R. Singireddy () and Manjanna Basappa ()
Additional contact information
Vishwanath R. Singireddy: Birla Institute of Technology and Science Pilani (Hyderabad Campus)
Manjanna Basappa: Birla Institute of Technology and Science Pilani (Hyderabad Campus)

Journal of Global Optimization, 2024, vol. 88, issue 1, No 9, 233-252

Abstract: Abstract In this paper, we study restricted variations of the following obnoxious facility location problem in the plane: locate k new obnoxious facilities amidst n ordered demand points (existing facility sites) in the plane so that none of the existing facility sites are affected. We study this problem in two restricted settings. The obnoxious facilities are constrained to be centered on (i) a predetermined horizontal line segment $${\overline{pq}}$$ pq ¯ , and (ii) the boundary arc of a predetermined disk $${{\mathcal {C}}}$$ C . For the problem in (i), we first give an $$(1-\epsilon )$$ ( 1 - ϵ ) -approximation algorithm that runs in $$O\left( (n+k)\log {\frac{||pq||}{2(k-1)\epsilon }}\right) $$ O ( n + k ) log | | p q | | 2 ( k - 1 ) ϵ time, where $$\epsilon >0$$ ϵ > 0 and ||pq|| is the length of $${\overline{pq}}$$ pq ¯ . We then propose two exact polynomial time algorithms, one based on doing binary search on all candidates and the other with the parametric search technique of Megiddo (J ACM 30:852–865, 1983); that will take $$O\left( (nk)^2 \right) $$ O ( n k ) 2 time and $$O\left( (n+k)^2 \right) $$ O ( n + k ) 2 time respectively. Continuing further, using the improved parametric technique, we give an $$O(n\log {n})$$ O ( n log n ) -time algorithm for $$k=2$$ k = 2 . We also show that the $$(1-\epsilon )$$ ( 1 - ϵ ) -approximation algorithm of (i) can be easily adapted to solve the problem (ii) with an extra multiplicative factor of n in the running time. Finally, we give a $$O(n^3k)$$ O ( n 3 k ) -time dynamic programming solution to the min-sum obnoxious facility location problem restricted to a line segment where the demand points are associated with weights, and the goal is to minimize the sum of the weights of the points covered.

Keywords: Continuous facility location; Approximation scheme; Parametric search; Segment tree; Dynamic programming; 68W25; 90C39; 68Q25 (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-023-01303-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:88:y:2024:i:1:d:10.1007_s10898-023-01303-x

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-023-01303-x

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().