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

DOI10.1016/J.TCS.2018.01.014zbMATH Open1387.05028OpenAlexW2787155382MaRDI QIDQ683750FDOQ683750

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

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

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)

Cites Work

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

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)