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

DOI10.1016/J.TCS.2018.01.014MaRDI QIDQ683750zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• The first approximation algorithm for the maximin Latin hypercube design problem
• Bounds for maximin Latin hypercube designs
• Construction of maximin distance Latin squares and related Latin hypercube designs
• An efficient local search-based genetic algorithm for constructing optimal Latin hypercube design
• On maximin distance and nearly orthogonal Latin hypercube designs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Maximin Latin Hypercube Designs in Two Dimensions
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Optimizing color picture tubes by high-cost nonlinear programming
• Paths, trees and matchings under disjunctive constraints
• The complexity of completing partial Latin squares

Cited in

(1)

• The first approximation algorithm for the maximin Latin hypercube design problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q683750)