Completion of partial Latin hypercube designs: NP-completeness and inapproximability

DOI10.1016/J.TCS.2018.01.014zbMath1387.05028OpenAlexW2787155382MaRDI QIDQ683750

Arpad Rimmel, Joanna Tomasik, Marc-Antoine Weisser, Kaourintin Le Guiban

Publication date: 9 February 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.01.014

zbMATH Keywords

NP-completenessinapproximabilityLatin hypercube designmaximin design

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Paths, trees and matchings under disjunctive constraints
• The complexity of completing partial Latin squares
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Optimizing color picture tubes by high-cost nonlinear programming
• Maximin Latin Hypercube Designs in Two Dimensions

This page was built for publication: Completion of partial Latin hypercube designs: NP-completeness and inapproximability