Completion of partial Latin Hypercube Designs: NP-completeness and inapproximability
| العنوان: | Completion of partial Latin Hypercube Designs: NP-completeness and inapproximability |
|---|---|
| المؤلفون: | Marc-Antoine Weisser, Kaourintin Le Guiban, Arpad Rimmel, Joanna Tomasik |
| المساهمون: | Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Graphes, Algorithmes et Combinatoire (LRI) (GALaC - LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS) |
| المصدر: | Theoretical Computer Science Theoretical Computer Science, Elsevier, 2018, 715, pp.1-20. ⟨10.1016/j.tcs.2018.01.014⟩ |
| بيانات النشر: | Elsevier BV, 2018. |
| سنة النشر: | 2018 |
| مصطلحات موضوعية: | [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Discrete mathematics, 021103 operations research, General Computer Science, Computer science, Generalization, Minimum distance, 0211 other engineering and technologies, Approximation algorithm, Field (mathematics), 0102 computer and information sciences, 02 engineering and technology, Minimax, 01 natural sciences, Theoretical Computer Science, Latin hypercube sampling, 010201 computation theory & mathematics, Completeness (order theory), ComputingMilieux_MISCELLANEOUS |
| الوصف: | Latin Hypercube Designs (LHDs) are crucial in the meta-modeling field. An LHD with maximal minimum distance between any pair of points guarantees a high quality of the model. We introduce a generalization of the Maximin LHD construction, the Maximin LHD completion, in which some points of the design are already fixed. We study the complexity of this problem and prove that it is NP-complete and it does not admit any approximation algorithm in most practical cases. |
| تدمد: | 0304-3975 1879-2294 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a9173c3520b3889fe0a08324ed8e8dce https://doi.org/10.1016/j.tcs.2018.01.014 |
| حقوق: | CLOSED |
| رقم الأكسشن: | edsair.doi.dedup.....a9173c3520b3889fe0a08324ed8e8dce |
| قاعدة البيانات: | OpenAIRE |
| تدمد: | 03043975 18792294 |
|---|