Covering a simplex by spheres: complexity and algorithms

Tongli Zhang and Yong Xia ()
Additional contact information
Tongli Zhang: Beihang University
Yong Xia: Beihang University

Journal of Global Optimization, 2022, vol. 84, issue 1, No 5, 119-135

Abstract: Abstract Simplex covering optimization problem (SCO) is modeled from the application of covering a simplex by m given balls. It contains the maximin dispersion problem as a special case. In this paper, we prove that (SCO) is NP-hard. We present an enumeration method (EM) to globally solve (SCO) and show that the complexity is strongly polynomial when m is fixed. Numerical experiments demonstrate that EM outperforms CPLEX when m is small. For larger m, we propose an efficient incomplete enumeration method based on linear programming relaxation.

Keywords: Simplex covering; Maximin dispersion; NP-hard; 90C26; 90C47; 90C20 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-022-01137-z 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:84:y:2022:i:1:d:10.1007_s10898-022-01137-z

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

DOI: 10.1007/s10898-022-01137-z

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 ().